無向グラフのDijkstraのアルゴリズム実装がJavaで動作しないのはなぜですか？

Question

有向グラフの実装がうまく動作します。索引付きのものではなく単純な優先度のキューを使用するため、「怠惰な」バージョンです。無向グラフの解を得るためにコードを変更しましたが、うまくいきません。 dijkstra(int s)はクラスGraphのメソッドです。 Graphの実装は、隣接関係のリストに基づいています。コード全体は、セジウィックの本の説明に基づいています。

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

Answer 1

私はそれを解決しました。愚かな間違い。代わり

vの縁

V-> W及びW->を追加するIを添加縁

V-> W及びW->

W

つまり、同じエッジを2回追加しました。逆エッジは作成されません。