贝尔曼-福特算法正确吗

Question

我一直试图通过以下资源来理解贝尔曼福特的正确实现：1

如果我们已经知道给定的加权有向图不包含一个圈（因此也没有负圈），是否遵循Bellman-Ford算法的正确实现？

int src = 0;
        int V = nodes.length; // 0 to n-1 nodes
        int E = edges.length;

        double[] distTo = new double[V];
        for (int i = 0; i < V; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        int[] edgeTo = new int[V];

        distTo[src] = 0.0;

        for (int i = 1; i < V - 1; i++) {

            double[] distToLocal = new double[V];
            for (int j = 0; j < V; j++) {
                distToLocal[j] = Double.POSITIVE_INFINITY;
            }

            for (int j = 0; j < E; j++) {

                int to = edges[i].to;
                int from = edges[i].from;
                int weight = edges[i].weight;

                if (distToLocal[to] > distTo[to] && distToLocal[to] > distTo[from] + weight) {
                    distToLocal[to] = distTo[from] + weight;
                    edgeTo[to] = from;
                }
              distToLocal[to] = Math.min(distToLocal[to],distTo[to]);

            }
            distTo = distToLocal;
        }

我在上述实现中遇到的第一个问题是，如果图中只有两个节点具有从源节点到目标节点的定向边，那么需要修改for的第一个循环，以0开始，而不是1，如下所示：

for (int i = 0; i < V - 1; i++) {

如果我做出上述改变，它仍然是正确的实现吗？

执行中的变化

如果不需要找到一个节点离src的最短距离，其中K是[0， V-1]，那么下面的变化似乎也能给出正确的结果。

int src = 0;
        int V = nodes.length; // 0 to n-1 nodes
        int E = edges.length;

        double[] distTo = new double[V];
        for (int i = 0; i < V; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        int[] edgeTo = new int[V];

        distTo[src] = 0.0;

        for (int i = 1; i < V - 1; i++) {

            /*double[] distToLocal = new double[V];
            for (int j = 0; j < V; j++) {
                distToLocal[j] = Double.POSITIVE_INFINITY;
            }*/

            for (int j = 0; j < E; j++) {

                int to = edges[i].to;
                int from = edges[i].from;
                int weight = edges[i].weight;

                if (distTo[to] > distTo[from] + weight) {
                    distTo[to] = distTo[from] + weight;
                    edgeTo[to] = from;
                }
            }
            //distTo = distToLocal;
        }

我想我理解了这种变化为什么有效，但是我很好奇为什么参考资料1没有提到这一点。

实现这种变体有什么缺点吗？显然，这种变体具有更好的内存需求。

注：我知道当加权有向图中没有圈时，我可以使用拓扑排序SPT算法，但我试图理解Bellman Ford的正确性。




Answer 1

Bellman-Ford算法指出，在V-1阶段松弛每个边缘后，将计算源到任何目的地之间的最小距离。在您的实现中，您运行每个阶段的V-2迭代。实际上，两个实现是相同的，您可以重用旧的距离数组。