1回答

liuyubobobo

2021-09-07

已采纳

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

继续加油！：）

1

1

甲骨文_0001

谢谢🙏

2021-09-07

共1条回复