最后的算法， BellmanFordFinal(s) 是上述3种算法的优化版本。
优化1：
在这本书中，著名的杰夫·埃里克森教授解释说，贝尔曼提出的原始算法是如何通过去除算法中最后3行的缩进来优化的。
因为最外层的迭代考虑每个边 u->v 只有一次，它们被处理的顺序并不重要。
优化2：
指数 i-1 已更改为 i 在最后两行中，这使算法能够更快地正确计算值（最短路径）。
优化3：
由于二维dp数组是不需要的，所以它被转换为一维。
因此，使用最后一个算法， BellmanFordFinal(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<=2-1，不正确。