<分区>
我们有一个有 100 个顶点的有向图。 v1 --> v2 --> ... v100 并且所有边的权重都等于 1。我们想使用 bellman-ford 来查找从 v1 到其他顶点的所有最短路径。该算法在每个步骤中以任意顺序检查所有边缘。如果在每一步中到所有其他顶点的最短距离 v1 都没有改变，则该算法停止。步骤的数量与检查边的顺序有关。这个问题的最小和最大步骤是多少？
解:2 和 100。
这个解决方案将如何实现？
<分区>
我们有一个有 100 个顶点的有向图。 v1 --> v2 --> ... v100 并且所有边的权重都等于 1。我们想使用 bellman-ford 来查找从 v1 到其他顶点的所有最短路径。该算法在每个步骤中以任意顺序检查所有边缘。如果在每一步中到所有其他顶点的最短距离 v1 都没有改变，则该算法停止。步骤的数量与检查边的顺序有关。这个问题的最小和最大步骤是多少？
解:2 和 100。
这个解决方案将如何实现？
最佳答案
如果边缘像，解是2
v1->v2
v1->v3
...
在这种情况下，第一次迭代将找到从源到每条边的距离，第二次迭代不会改变任何权重，因此算法停止
解是100，如果
v1->v2->v3->...->v100
.即所有都在一条直线上，我们需要 99 次迭代来更新到第 100 个顶点的距离，最后一次迭代不会改变距离。
关于algorithm - Bellman-Ford 算法的变体？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35526126/