Bellman Ford 随机产生错误结果

Question

我正在尝试从 CLRS 中实施 Bellman Ford 算法，但它似乎在距离度量上随机溢出。我的代码如下：

private void initSingleSource(Vertice source) {
    for(Vertice vertice:vertices) {
        vertice.distance = Integer.MAX_VALUE;
        vertice.predecessor = null;
    }
    source.distance = 0;
}

private void relax(Vertice u, Vertice v, int weight) {
    if(v.distance > u.distance + weight) {
        v.distance = u.distance + weight;
        v.predecessor = u;
    }
}

public boolean bellmanFord(Vertice source) {
    initSingleSource(source);
    for(int i = 0; i < vertices.size()-1; i++) {
        for(Vertice u: edges.keySet()) {
            Hashtable<Vertice, Integer> table = edges.get(u);
            for(Vertice v: table.keySet()) {
                 relax(u, v, table.get(v));
            }
        }
    }
    for(Vertice u: edges.keySet()) {
        Hashtable<Vertice, Integer> table = edges.get(u);
        for(Vertice v: table.keySet()) {
             if(v.distance > u.distance + table.get(v)) {
                 return false;
             }
        }
    }

    return true;
}

代码的输入是：

g.addAdjList(A, B, 6);
g.addAdjList(A, D, 7);
g.addAdjList(B, C, 5);
g.addAdjList(B, D, 8);
g.addAdjList(B, E, -4);
g.addAdjList(C, B, -2);
g.addAdjList(D, C, -3);
g.addAdjList(D, E, 9);
g.addAdjList(E, C, 7);
g.addAdjList(E, A, 2);

我随机得到的正确答案是：

B 2 C 4 D 7 E -2

否则我得到：

B -2147483636 C -2147483634 D -2147483631 E -2147483640

知道为什么会这样吗？

Answer 1

我认为当用 u 调用 relax 使得 u.distance 等于 Integer.MAX_VALUE 时，问题就出现了。然后 u.distance + weight 为负（总和超出范围）。该负值小于 v.distance 并被分配给 v.distance.

这可能会发生，也可能不会发生，具体取决于 relax 调用的顺序。顺序是随机的，因为您使用 table.keySet()。如果您有幸按照 DFS 的顺序考虑顶点，您应该会得到正确的结果，但这不太可能。

可能的解决方案

private void relax(Vertice u, Vertice v, int weight) {
    if(u.distance != Integer.MAX_VALUE && v.distance > u.distance + weight) {
        v.distance = u.distance + weight;
        v.predecessor = u;
    }
}

Bellman Ford 随机产生错误结果

Bellman Ford randomly producing wrong results

java

algorithm

bellman-ford