java - 無向グラフ用の Java での Dijkstra のアルゴリズムの実装が機能しないのはなぜですか?

Question

私の有向グラフの実装は正常に動作します。インデックス付きキューの代わりに単純な優先度キューを使用するため、これは「怠惰な」バージョンです。無向グラフの解決策を得るためにコードを変更しましたが、機能しません。dijkstra(int s)クラスのメソッドですGraph。の実装はGraph、隣接リストに基づいています。コード全体は Sedgewick の本の説明に基づいています。

public void dijkstra(int s) {

    marked = new boolean[V];
    distTo = new int[V];
    edgeTo = new Edge[V];

    Comparator<Edge> comparator = new Comparator<Edge>() {

        public int compare(Edge e1, Edge e2) {

            int dist1 = distTo[e1.either()] + e1.weight();
            int dist2 = distTo[e2.either()] + e2.weight();

            if (dist1 < dist2) {
                return -1;
            } else if (dist1 > dist2) {
                return 1;
            } else {
                return  0;
            }
        }
    };

    pq = new PriorityQueue<Edge>(comparator);

    for (int v = 0; v < V; ++v) {
        distTo[v] = Integer.MAX_VALUE;
    }

    distTo[s] = 0;

    relax(s);

    while (!pq.isEmpty()) {

        Edge e = pq.poll();

        int v = e.either();
        int w = e.other(v);

        if (!marked[w]) {
            relax(w);
        }
    }
}

private void relax(int v) {

    marked[v] = true;

    for (Edge e : adj[v]) {

        int w = e.other(v);

        if (distTo[w] > distTo[v] + e.weight()) {

            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            pq.add(e);
        }
    }
}