2

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

所有边的权重都是 1。我们想使用Bellman-Ford算法找到顶点 1(V_1)到其他顶点之间的最短路径。该算法在每个步骤中以任意顺序检查所有边缘。如果一步V_1中所有其他顶点之间的最短路径not changed（来自先前的值），则算法将停止！the number of steps in this algorithms depends on the order of inspecting edges.

这个算法的最大和最小步数是多少？

a) 100, 10000

b) 2, 100

c) 100, 100

d) 2, 99

谁能描述我为什么选择选项（2）来回答这个问题？

4

1 回答 1

0

Bellman-Ford 算法在Wikipedia中给出。

如果V_1和V_2被选中，这是两个步骤。V_1假设to不是一个允许的输入，它不会变得更好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和之间有 99 条边V_100，因为E_99从V_99到V_100。这将采取多少步骤？这个特定的图表可以有更长的路径吗？

于 2015-03-03T13:48:26.747 回答