algorithm - Bellman-Ford 算法和步骤数

Question

假设有一个有100-Vertexes 的有向图，例如V_1---> V_2 ---> ... ---> V_100

所有边的权重都是 1。我们想使用 Bellman-Ford 算法找到顶点 1 (V_1) 到其他顶点之间的最短路径。该算法在每个步骤中以任意顺序检查所有边缘。如果在一个步骤中 V_1 到所有其他顶点之间的最短路径未更改(从以前的值)，算法将停止!。 此算法中的步骤数 取决于检查边缘的顺序。

what is the Max and Min number of steps in this algorihms?

a) 100, 10000

b) 2, 100

c) 100, 100

d) 2, 99

谁能告诉我为什么选择选项 (2) 作为这个问题的答案？

Answer 1

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。

第 1 步:从头开始，即我们知道从 V_1 到 V_1 的最短路径。
第 2 步:沿着其中一条边。只有一条边，我们称之为 E_1。这条边从 V_1 到 V_2。该算法将遵循此边缘。现在我们从 V_1 到 V_2 的最短路径沿着这条边走了 1 步。 V_1 和 V_2 的步数为 2。这是最短的非平凡路径。

现在确定 V_1 和 V_100 之间的距离的结果。 V_1 和 V_100 之间有 99 条边，因为 E_99 从 V_99 到 V_100 >。这需要多少步？这个特定的图可以有更长的路径吗？