algorithm - 贝尔曼-福特算法的变化？

Question

我们有一个有 100 个顶点的有向图。v1 --> v2 --> ... v100 并且所有边的权重都等于 1。我们想使用 bellman-ford 来查找从 v1 到其他顶点的所有最短路径。该算法在每一步中以任意顺序检查所有边。如果在每一步中到所有其他顶点的最短距离 v1 没有改变，则该算法停止。步数与检查边的顺序有关。这个问题的最小和最大步数是多少？

解决方案：2 和 100。

这个解决方案将如何实现？

Answer 1

如果边缘像，则解决方案为 2

v1->v2
v1->v3
...

在这种情况下，第一次迭代将找到从源到每个边的距离，第二次迭代不会改变任何权重，因此算法停止

解是 100，如果

v1->v2->v3->...->v100 

.ie都在一条直线上，比我们需要99次迭代来更新到第100个顶点的距离，最后一次迭代不会改变距离。