Dijkstra算法与Adjaceny矩阵

Question

我正在尝试使用给定邻接矩阵的优先级队列实现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])); 
      } 
     } 
    } 
}