Adjaceny 행렬이있는 Dijkstra 알고리즘

Question

adjaceny 행렬이 주어진 우선 순위 큐를 사용하여 Dijkstra 알고리즘을 구현하려고합니다. 문제는 아마도 우선 순위 큐에 버텍스를 추가하는 곳에서 발생하지만 문제를 해결하는 방법을 찾을 수 없다는 것을 알고 있습니다!

static int dijkstra(int[][] g, int i, int j) { 
    // Get the number of vertices in G 
    int n = g.length; 
    int counter = 0; 

    PriorityQueue<Vertex> q = new PriorityQueue<Vertex>(n, new Comparator<Vertex>() {  
     public int compare(Vertex a, Vertex b) { 
      Vertex v1 = (Vertex) a; 
      Vertex v2 = (Vertex) b; 
      if (v1.getD() > v2.getD()) { 
       return 1; 
      } else if (v1.getD() < v2.getD()) { 
       return -1; 
      } else { 
       return 0; 
      } 
     } 
    }); 
    int[] distance = new int[n]; 
    for (int l = 0; l < n; l++) { 
     distance[l] = 99999; 
    } 
    distance[i] = 0; 

    for (int l = 0; l < n/2; l++) { 
     for (int m = 0; m < n; m++) { 
      if (g[l][m] > 1) { 
       System.out.printf("%d was added \n", g[l][m]); 
       q.add(new Vertex(l, g[l][m])); 
      } 
     } 
    } 
    while (!q.isEmpty()) { 
     int u = 0; 
     for (int z = 0; z < n; z++) { 
      if (distance[z] < distance[u]) { 
       u = z; 
      } 
     } 
     if (distance[u] == 99999) { break; } 
     q.remove(); 
     for (int l = 0; l < n; l++) { 
      if (g[u][l] > 1) { 
       int alt = distance[u] + g[u][l]; 
       if (alt < distance[l]) { 
        distance[l] = alt; 
        q.remove(); 
        q.add(new Vertex(u, distance[l])); 
       } 
      } 
     } 
    } 

    for (int k = 0; k < n; k++) { 
     System.out.printf("==>%d", distance[j]); 
    } 
    return distance[j]; 
} 

그리고 : 나는 다음과 같은 매트릭스 테스트입니다

class Vertex { 
    int v,d; 
    public Vertex(int num, int dis) { 
     v = num; 
     d = dis; 
    } 
    public int getV() { 
     return v; 
    } 
    public int getD() { 
     return d; 
    } 
} 

:

0 0 0 0 0 0 0 38 0 0 0 0 0 0 0 0 
0 0 0 0 65 0 64 0 6 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 6 8 0 0 0 62 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 65 0 0 0 0 0 0 0 6 0 0 0 0 55 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 64 0 0 0 0 0 53 0 0 36 0 45 0 0 0 
38 0 0 0 0 0 53 0 0 0 0 91 0 29 0 0 
0 6 0 0 0 0 0 0 0 0 0 95 55 0 0 0 
0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 
0 0 6 0 0 0 36 0 0 0 0 0 0 0 0 0 
0 0 8 0 0 0 0 91 95 0 0 0 60 0 0 0 
0 0 0 0 0 0 45 0 55 0 0 60 0 0 0 0 
0 0 0 0 0 0 0 29 0 0 0 0 0 0 0 0 
0 0 0 0 55 0 0 0 0 0 0 0 0 0 0 0 
0 0 62 0 0 0 0 0 0 0 0 0 0 0 0 0 

그리고 시작은 0입니다, 끝이 n - 1입니다. 나는 195를 얻고 있어야한다. 그러나 그것은 거리의 어떤 것도 바뀌지 않는 것처럼 보인다!

Answer 1

거리를 인쇄 할 때 배열은 항상 j이고 k은 반복기입니다. 거리는 일정하게 보이지만 변화하고 있습니다.

for (int k = 0; k < n; k++) { 
    System.out.printf("==>%d", distance[k]); 
} 

또한 알고리즘에서 상위 꼭지점을 두 번 제거하는 것이 그럴 수 있습니다. 알고리즘은 다음과 같이되어야합니다.

while (!q.isEmpty()) { 
    int u = q.peek().v; 
    q.remove(); 
    for (int l = 0; l < n; l++) { 
     if (g[u][l] > 1) { 
      int alt = distance[u] + g[u][l]; 
      if (alt < distance[l]) { 
       distance[l] = alt; 
       q.add(new Vertex(u, distance[l])); 
      } 
     } 
    } 
}