我们有一个有100个顶点的有向图 . v1 - > v2 - > ... v100并且所有边权重等于1.我们希望使用bellman-ford来查找从v1到其他顶点的所有最短路径 . 每个步骤中的该算法以任意顺序检查所有边缘 . 如果在每个步骤中没有改变到所有其他顶点的最短距离v1，则该算法停止 . 步数与检查边的顺序有关 . 此问题的最小步骤和最大步数是多少？
解决方案：2和100 .
如何实现这个解决方案？
如果边缘是这样，解决方案是2
v1->v2 v1->v3 ...
在这种情况下，第一次迭代将找到从源到每个边缘的距离，并且第二次迭代将不会改变任何权重，因此算法停止
如果是，解决方案是100
v1->v2->v3->...->v100
.i.e . 所有都是直线，比我们需要99次迭代来更新到第100个顶点的距离，最后一次迭代不会改变距离 .
1 回答
如果边缘是这样，解决方案是2
在这种情况下，第一次迭代将找到从源到每个边缘的距离，并且第二次迭代将不会改变任何权重，因此算法停止
如果是，解决方案是100
.i.e . 所有都是直线，比我们需要99次迭代来更新到第100个顶点的距离，最后一次迭代不会改变距离 .