algorithm - 贝尔曼福特算法的旧考试，需要一个 indea 吗？

Question

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

解决方案：2 和 100。

我认为：

如果我们有这个图：v1->v2->v3->...->v100，我们需要 2。如果我们有 V1->v2，V1->V3，V1->V4，...我们需要 100。最后，如果我们有 v99v100,v98v99,...,v3v2,v2v1，我们再次需要 100。

任何人都可以帮助或验证我吗？

Answer 1

v1->v2->v3->...->v100 我们需要 2

没错，假设您按顺序获得边缘（v1->v2、v2->v3、v3->v4...）。

V1->v2, V1->V3, V1->V4 ...我们需要 100。

错误，因为所有距离都是 1（从起始节点到所有其他节点有一条直接边），那么在一次通过边缘时，您将获得正确的结果（无论边缘的顺序如何），并且第二关停止。

v99v100,v98v99,...,v3v2,v2v1 我们需要 100。

没错，假设您有与第一个示例相同的图形，但边的顺序相反。