DijkstraSP issue

[fengxiaohu]

I am confusing about the judgement of consitency of edgeTo[v] and distTo[v] Here is the code:

private boolean check(EdgeWeightedDigraph G, int s) {

    // check that edge weights are nonnegative
    for (DirectedEdge e : G.edges()) {
        if (e.weight() < 0) {
            System.err.println("negative edge weight detected");
            return false;
        }
    }

    // check that distTo[v] and edgeTo[v] are consistent
    if (distTo[s] != 0.0 || edgeTo[s] != null) {
        System.err.println("distTo[s] and edgeTo[s] inconsistent");
        return false;
    }
    for (int v = 0; v < G.V(); v++) {
        if (v == s) continue;
        if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
            System.err.println("distTo[] and edgeTo[] inconsistent");
            return false;
        }
    }

    // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight()
    for (int v = 0; v < G.V(); v++) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[v] + e.weight() < distTo[w]) {
                System.err.println("edge " + e + " not relaxed");
                return false;
            }
        }
    }

    // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight()
    for (int w = 0; w < G.V(); w++) {
        if (edgeTo[w] == null) continue;
        DirectedEdge e = edgeTo[w];
        int v = e.from();
        if (w != e.to()) return false;
        if (distTo[v] + e.weight() != distTo[w]) {
            System.err.println("edge " + e + " on shortest path not tight");
            return false;
        }
    }
    return true;
}

I think if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) should be if (edgeTo[v] == null && distTo[v] == Double.POSITIVE_INFINITY)

 // check that distTo[v] and edgeTo[v] are consistent
    if (distTo[s] != 0.0 || edgeTo[s] != null) {
        System.err.println("distTo[s] and edgeTo[s] inconsistent");
        return false;
    }
    for (int v = 0; v < G.V(); v++) {
        if (v == s) continue;
        if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
            System.err.println("distTo[] and edgeTo[] inconsistent");
            return false;
        }
    }

[kevin-wayne]

I believe it's correct as is. A vertex is not reachable from s if and only if both edgeTo[v] = null and distTo[v] = infinity. So, if edgeTo[v] is null but distTo[v] is finite, something went wrong.

[fengxiaohu]

Got it,thank you very much