Почему моя реализация алгоритма Дейкстры в 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-> ш и w-> v

Я добавил края

v-> ш и w-> ш

т.е. я дважды добавил тот же край, не создавая обратный край.