Bellman-Ford实施和同时放松

Question

最近，我看到了贝尔曼·福特的问题和一些事实如下：

我们知道bellman-ford算法在每个步骤中检查所有边，对于每个边，如果，d（v）

对于在具有n顶点的图G中查找顶点s的所有最短路径，此算法在k之后终止

以下事实是真实的。

来自s的所有最短路径中的边数最多为k-1

在这本书中，我们有3个BFord的实现（一些优化）。我的问题是，如果我们同时有松弛，应该使用这些算法中的哪一个，通过使用它，上述事实应该是正确的？或者不是一般的上述事实是否属实？




Answer 1

最后的算法，BellmanFordFinal（s）是上述三种算法的优化版本。

优化1：

在这本书中，传奇人物杰夫·埃里克森教授解释了贝尔曼提出的原始算法是如何通过去除算法中最后3行的缩进来优化的。

因为最外层的迭代考虑每个边u-

优化2：

在最后两行中，索引i-1已更改为i，这使算法能够更快地正确计算值（最短路径）。

优化3：

二维DP阵列被转换为一维，因为它是不必要的。

因此，请使用最终算法，标题为BellmanFordFINE（s）。

事实上，我们需要在N-1时间内运行最外层的循环，这始终是正确的，并且与任何实现无关，因为在线性图的情况下，从源到目标的最长最短路径将是N-1，其中N是图中的节点数。

回答您对k-1的担忧

从s开始的所有最短路径中的边数最多为k-1

上述语句取决于算法的实现。

如果添加If条件以在没有任何边进一步松弛时打断最外面的循环，则此语句为false。

否则是真的。

看看我在https://cp-algorithms.com/graph/bellman_ford.html上发现的以下实现：

void solve()
{
    vector<int> d (n, INF);
    d[v] = 0;
    for (;;)
    {
        bool any = false;

        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                if (d[e[j].b] > d[e[j].a] + e[j].cost)
                {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;
                }

        if (!any) break;
    }
    // display d, for example, on the screen
}

变量any用于检查它们是否在任何迭代中完成了任何松弛。如果没有做到，打破循环。

因此，可能会发生循环提前终止的情况，例如，当k=2且最长最短路径中的边数为3时。现在，3个