假设有一个带100-Vertexes的有向图，例如V_1---> V_2 ---> ... ---> V_100
所有边的权重都是1。我们希望使用Bellman-Ford算法来找到顶点1(V_1)到其他顶点之间的最短路径该算法在每一步都以任意顺序检查所有边。如果在一个步骤中V_1到所有其他顶点之间的最短路径not changed（从以前的值），算法将停止！.the number of steps in this algorithmsdepends on the order of inspecting edges。
这个算法的最大和最小步数是多少？
a) 100, 10000
b) 2, 100
c) 100, 100
d) 2, 99
任何人都可以描述为什么选择选项（2）来回答这个问题？
最佳答案
Bellman-Ford算法在Wikipedia中给出。
如果选择V_1和V_2，这是两个步骤。假设V_1到V_1不是一个允许的输入（可以通过一个步骤来完成），就不会有更好的结果。
最坏的情况是如果V_1和V_100作为输入：这需要100步才能达到v_100。
问题是：给定可能的输入，对于示例图中的边与边之间的距离，什么是最好的，什么是最坏的情况？
示例：输入为Bellman-Ford(Vertices, Edges, Soucre)
会发生什么？
在这个特定的例子中，顶点是v_1到v_100，边是e_1（从v_1到v_2，等等），源是v_1。
第一步：从头开始，即我们知道从V_1到V_1的最短路径。
第二步：沿着其中一条边走只有一条边，我们称之为E_1。此边从V_1到V_2。算法将遵循此边。现在，从V_1到V_2的最短路径沿着这条边走了一步vu 1和vu 2的步数是2。这是最短的非平凡路径。
现在确定v_1和v_100之间距离的结果。V_1和V_100之间有99条边，因为E_99从V_99变为V_100。这要走多少步？这个特定的图能有一个更长的路径吗？
关于algorithm - Bellman-Ford算法和步骤数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28833375/