我了解到Bellman-Ford算法的运行时间为O（| E | * | V |），其中E是边数，V是顶点数 . 假设图表没有任何负加权周期 .
我的第一个问题是，我们如何证明在（| V | -1）迭代内（每次迭代检查E中的每个边），在给定特定的起始节点的情况下，它会更新到每个可能节点的最短路径？我们有可能迭代（| V | -1）次但仍然没有以最短的路径到达每个节点吗？
假设算法的正确性，我们实际上可以做得更好吗？在我看来，并非所有边都在特定图中被负加权 . 贝尔曼 - 福特算法似乎很昂贵，因为每次迭代它都经过每一个边缘 .
1 回答
从源到任何顶点的最长路径最多将涉及图中的所有其他顶点 . 换句话说 - 你不会有一条经过同一个顶点的路径不止一次，因为这必然会增加权重（这是正确的，因为没有负循环） .
在每次迭代中，您将更新此路径中下一个顶点的最短路径权重，直到| V | -1次迭代后，您的更新必须到达该路径的末尾 . 之后，将不会有任何具有非紧密值的顶点，因为您的更新已覆盖了该长度的所有最短路径 .
这种复杂性很紧张（至少对于BF而言），想想一长串连接的顶点 . 选择最左边的作为源 - 您的更新过程必须一次从顶点到另一侧 . 现在你可能会争辩说你不必检查每条边缘，所以让我们抛出一些重量非常大的随机边缘（N> | V | * max-weight） - 它们无法帮助你，但是你的算法肯定不知道，所以如果必须经历用这些权重更新顶点的过程（它们仍然优于初始无穷大） .