对松驰操作的疑问

Question

老师, 对图中每一条边，至少进行V-1次松驰操作，但是无向图每条边都有两个方向，所以我脑海中是认为2*(V-1)次松驰操作
才能确定从源s点到图中其它点的最短距离

Answer 1

liuyubobobo 2021-09-07 15:18:49

bellman-ford 算法需要 V - 1 轮松弛操作，这是和整张图中有多少边无关。整张图中有多少边，影响的是每一轮松弛操作要处理多少内容（每轮松弛操作要将所有的边松弛一遍。）

之所以进行 V - 1 次操作，是因为最短路最多只能经过 V 个顶点（即图中每个顶点都走一次）。

是的，对于无向图，在每一轮松弛操作中，每一条边的两个方向都要松弛。我们的代码也没有问题：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/12-Shortest-Path/08-Bellman-Ford-Algorithm/src/BellmanFord.java

在 22-23 这两重循环中，我们会将每一条边的两个方向取出来。这是因为对于我们的无向图存储，对于 v-w 这条边，g[v] 中会有 w，g[w] 中会有 v，对应我们建图代码的 41-42 行：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/12-Shortest-Path/08-Bellman-Ford-Algorithm/src/WeightedGraph.java

继续加油！：）

• 提问者 甲骨文_0001 #1

  谢谢🙏