贝尔曼福特算法的正确性，我们还能做得更好吗？

Question

我了解到，Bellman-Ford算法具有O（| e | * | v |）的运行时间，其中E是边缘的数量和V的顶点数量。假设图表没有任何负加权循环。

我的第一个问题是我们如何证明在（| v | -1）迭代中（每次迭代检查e中的每个边缘），它会给定个特定的启动节点更新每个可能节点的最短路径吗？我们是否有可能迭代（| v | -1）次，但仍未以每个节点的最短路径结束？

假设算法的正确性，我们可以实际上做得更好吗？它发生在我上，并非所有边缘都在特定图表中负载。Bellman-Ford算法似乎昂贵，因为每次迭代都会通过每个边缘。

Answer 1

从源到任何顶点的最长可能的路径将涉及图表中的大多数其他顶点。换句话说 - 你不会多次通过相同的顶点的路径，因为这必然会增加权重（这是真的，只有没有负循环）。 在每次迭代时，您将在此路径中的下一个顶点上更新最短路径权重，直到v | -1迭代您的更新必须到达该路径的结尾。之后不会有任何具有非严格值的顶点，因为您的更新已介绍了最短的路径，直到该长度。

这种复杂性紧密（至少为BF），想想长线连接顶点。选择最左边的来源 - 您的更新过程必须在一次从那里到另一侧的方式工作。现在你可能会争辩说你不必检查每个边缘，所以让我们扔几个随机边缘，重量非常大（n> | v | * max-prefice） - 他们无法帮助你，但是您的算法肯定无法知道，所以如果必须通过这些权重更新顶点的过程（它们仍然比初始无穷大）更新。