如何使行李员-福特在最坏的情况下运行？

Question

我试图使优化版本的贝尔福特算法在最坏的情况下运行。优化版本我的意思是，如果放松1轮边缘，没有进一步更新的最短距离，它终止。

例如，一个具有7个顶点的简单连通加权有向图，从源顶点0运行优化的Bellman算法需要至少5轮才能得到正确的最短路径。

该图表不能包含负重循环。即，处理顶点0的所有传出边，然后处理顶点1的边缘，以此类推。

我知道这和周期有关。但是，我不太确定的策略，在绘制图表，以满足要求。

Answer 1

您的Bellman算法版本将需要与图中所有最短路径的最长长度(以边为单位)一样多的迭代。

考虑具有n个顶点的有向图。把边1 -> 2 -> 3 -> . -> n加到图中，每个边都有一个小的正权重。然后，您可以添加任意多的沉重边，你想要。很明显，从1到n的最短路径长度为n-1。因此，您的算法将需要严格的n-1迭代。

此外，还有一个改进版本的Bellman算法.它被称为最短路径快速算法。虽然它有一个最坏的运行时间的O(|V|*|E|)，这是相同的贝尔-福特，很少有图表可以使算法达到那个时间。实际上，您可以预期O(|E|)的平均运行时(未经验证)。