Dijkstra 무 방향 그래프의 최단 경로

Question

다음 코드는 유향 그래프에서 완벽하게 작동하며 무향 그래프가 주어지면 최단 경로를 반환하지 않습니다.

public void Djikstra(int s){ 
    boolean[] marked = new boolean[V]; 
    dist = new double[V]; 

    for(int i = 0; i<V; i++){ # initializing array 
     dist[i] = Double.POSITIVE_INFINITY; 
    } 
    dist[s] = 0.0; 

    Queue<Integer> pqs = new PriorityQueue<Integer>(); 

    pqs.add(s); 
    while(!pqs.isEmpty()){ 
     int v = pqs.poll(); 

     if(marked[v]) continue; 
     marked[v] = true; 

     for(Edge e : get_list(v)){ # get_list(v) will return an iterable from the adjacency list at index v 
      v = e.getV() 
      int w = e.getW(); 
      if(dist[w] > dist[v] + e.getWeight()){ 
       dist[w] = dist[v] + e.getWeight(); 
       distances[w] = e #all the distances will be stored in this array 
       pqs.add(w); 
      } 
     } 
    } 
} 

여기 내 실수는 무엇입니까? 나는 그것이 단순한 오류라고 확신합니다. 몇 가지 힌트가 그 일을 할 것입니다.

감사합니다.

편집 :

public void addEdge(Edge e){ 
    adj[e.getV()].add(e); 
    adj[e.getW()].add(e); 
} 

Answer 1

가 (당신이 방향 그래프에 추가 할 필요가 무엇 2.

에 노드 1에서 2 노드 1에서 지시 된 경로 사이의 차이와 무향 경로를 고려 귀하의 알고리즘이 해결할 수있는) 무 방향성 그래프와 동일하게 만들 수 있습니까?

편집 :

생각해보십시오. 여기에 힌트가 있습니다 : 당신은 현재 for 루프 안의 리셋 v를 바꾸고 있습니다. 이것은 유향 그래프에서 오류를 일으키지 않지만 에지가 v에서 w로 이동하지 않고 w에서 v로 나열되면 어떻게됩니까?

EDIT2 :

이 같은

뭔가 :

먼저, 이것은 당신의 가장자리의 어느 정점에 승의 값을 설정 int w = (v == e.getV()) ? e.getW() : e.getV();

에 다음 줄을 변경, v = e.getV();

두 번째를 제거 v는 NOT입니다.

이 두 번째 제안은 (어쩌면 조금 더 쉽게 읽는) 다음에 해당 : 당신은 두 개의 서로 다른 가장자리, 직접 및 역을 추가해야

int w = e.getW(); 
if (w == v) { 
    w = e.getV(); 
} 

Answer 2

. 당신이 가장자리를 추가 할 때, 다음과 같이 그것을 할

public void addEdge(Edge e){ 
    adj[e.getV()].add(e); 
    adj[e.getW()].add(e); 
} 

public void addEdge(Edge e){ 
    adj[e.getV()].add(e); 
} 

에서

및 변경 : 무 방향 그래프의

Edge e = new Edge(from, to, weight); 
Edge f = new Edge(to, from, weight); 

addEdge(e); 
addEdge(f);