2

我正在尝试从 CLRS 实现贝尔曼福特算法，它似乎随机溢出距离度量。我的代码如下：

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

知道为什么会这样吗？

4

1 回答 1

2

我认为当使用 equlas 调用时会出现relax问题。然后是负数（总和超出范围）。该负值小于并分配给。uu.distanceInteger.MAX_VALUEu.distance + weightv.distancev.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;
    }
}
于 2015-01-22T09:28:42.653 回答