我了解到贝尔曼-福特算法的运行时间为O(|E|*|V|)，其中E是边数，V是顶点数。假设该图没有任何负加权循环。
我的第一个问题是，我们如何证明在 (|V|-1) 次迭代（每次迭代检查 E 中的每条边）内，给定特定的起始节点，它更新到每个可能节点的最短路径？有没有可能我们已经迭代了 (|V|-1) 次但仍然没有得到到每个节点的最短路径？
假设算法是正确的，我们实际上可以做得更好吗？我突然想到，在特定的图中，并非所有边都具有负权重。贝尔曼-福特算法看起来很昂贵，因为每次迭代都会遍历每条边。
从源到任何顶点的最长可能路径将最多涉及图中的所有其他顶点。换句话说 - 您不会有一条多次经过同一顶点的路径，因为这必然会增加权重（这只是由于不存在负循环这一事实而成立）。
在每次迭代中，您将更新该路径中下一个顶点的最短路径权重，直到 |V|-1 次迭代之后，您的更新必须到达该路径的末尾。之后，将不会有任何具有非紧值的顶点，因为您的更新已覆盖达到该长度的所有最短路径。
这种复杂性是很严格的（至少对于 BF 而言），想象一下一长串相连的顶点。选择最左边的作为源 - 您的更新过程必须一次从那里到另一边一个顶点。现在你可能会说你不必以这种方式检查每条边，所以让我们加入一些具有非常大权重的随机边（N > |V|*max-weight） - 它们无法帮助你，但是您的算法无法确定这一点，因此必须经历使用这些权重更新顶点的过程（它们仍然比初始无穷大更好）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
