Bellman Ford randomly producing wrong results

Question

I'm trying to implement the Bellman Ford Algorithm from CLRS, and it randomly seems to overflow on the distance metric. My code is as follows:

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;
}

Input for the code is:

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);

The correct answer, which I randomly get is:

B 2 C 4 D 7 E -2

Otherwise I get:

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

Any idea why this is happening?

Answer 1

I think the problem arises when relax is called with u such that u.distance equlas Integer.MAX_VALUE. Then u.distance + weight is negative (the sum goes out of bounds). That negative value is smaller than v.distance and gets assigned to v.distance.

That may happen or not, depending on the order of relax calls. The order is random, as you use table.keySet(). If you have the luck to consider vertices in the order that DFS would do, you should get correct results, but that is not likely.

Possible solution

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;
    }
}