algorithm - Bellman-Ford 算法的正确性，我们还能做得更好吗？

Question

我了解到 Bellman-Ford 算法的运行时间为 O(|E|*|V|)，其中 E 是边数，V 是顶点数。假设图中没有任何负加权循环。

我的第一个问题是，我们如何证明在 (|V|-1) 次迭代内(每次迭代检查 E 中的每条边)，给定一个特定的起始节点，它会更新到每个可能节点的最短路径？是否有可能我们已经迭代 (|V|-1) 次但仍然没有以到每个节点的最短路径结束？

假设算法的正确性，我们真的可以做得更好吗？我突然想到，并不是所有的边在特定的图中都是负权重的。 Bellman-Ford 算法看起来很昂贵，因为它的每次迭代都要经过每条边。

Answer 1

从源到任何顶点的最长可能路径最多涉及图中的所有其他顶点。换句话说 - 你不会有一条路径多次通过同一个顶点，因为这必然会增加权重(这是真的，因为没有负循环的事实)。
在每次迭代中，您将更新此路径中下一个顶点的最短路径权重，直到 |V|-1 次迭代后，您的更新必须到达该路径的末尾。之后将不会有任何具有非紧值的顶点，因为您的更新已经覆盖了达到该长度的所有最短路径。

这种复杂度非常高(至少对于 BF 而言)，想想一长串相连的顶点。选择最左边的作为源——你的更新过程必须一次从那里到另一边一个顶点。现在你可能会争辩说你不必那样检查每条边，所以让我们随机添加一些权重非常大的边 (N > |V|*max-weight) - 它们帮不了你，但是您的算法无法确定这一点，因此 if 必须经历使用这些权重更新顶点的过程(它们仍然比初始无穷大更好)。