假设有一个有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) 作为这个问题的答案?
最佳答案
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
>。这需要多少步?这个特定的图可以有更长的路径吗?
关于algorithm - Bellman-Ford 算法和步骤数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28833375/