视频字幕
Bellman-Ford算法是一种用于计算带权图中单源最短路径的算法。它的主要特点是可以处理负权边，能够检测负权环，时间复杂度为O(V乘以E)，其中V是顶点数，E是边数。该算法适用于有向图和无向图。与Dijkstra算法相比，Bellman-Ford可以处理负权边，但时间复杂度较高。
Bellman-Ford算法基于松弛操作原理。算法分为三个主要步骤：首先，初始化源点距离为0，其他顶点距离为无穷大；然后，对图中所有边进行V-1次松弛操作，其中V是顶点数；最后，再次遍历所有边检查是否存在负权环。松弛操作是指：对于边(u,v)，如果从源点经过u到v的距离小于当前已知的从源点到v的距离，则更新v的距离值。经过V-1次迭代后，如果没有负权环，所有顶点的最短路径距离都已确定。
让我们通过一个具体示例来演示Bellman-Ford算法的第一次迭代。初始状态下，源点A的距离为0，其他顶点B、C、D的距离都是无穷大。首先松弛边A到B，距离更新为1；然后松弛边A到C，距离更新为4；接着松弛边B到C，因为1加3大于4，所以C的距离不变；松弛边B到D，D的距离更新为3；最后松弛边C到D，因为4加负3等于1，小于当前D的距离3，所以D的距离更新为1。第一次迭代结束后，各顶点的距离为：A=0，B=1，C=4，D=1。
现在我们来看Bellman-Ford算法的C++实现。代码中使用Edge结构体存储边的信息，包括起点、终点和权重。算法的核心部分是两个循环：外层循环进行V-1次迭代，内层循环遍历所有边并执行松弛操作。代码中包含了一个优化：如果某次迭代中没有任何距离更新，说明已经找到了最短路径，可以提前退出循环。最后，再次遍历所有边检查是否存在负权环。如果存在负权环，则报告最短路径不存在；否则，输出从源点到各顶点的最短距离。对于我们的示例图，最终结果是：A=0，B=1，C=4，D=1。