用Java实现Dijkstra算法的图？

Question

所以我试图用Java实现Dijkstra的算法。我知道有不同的方法可以做到这一点，但以下是我学会的方法。所以我从一个顶点开始，找到从这个顶点到其他顶点的最短路径。我从一个顶点开始（在我的例子中是零），然后通过放松连接到该顶点的所有边来更新我的邻域。然后找出连接到当前边的最小边，然后将该顶点添加到顶点存储中。我一直这样做，直到所有的顶点都在我的顶点存储中，然后我应该得到一种生成树，它显示了所有的最短路径

所以在我的代码中，我试图找到从0到1的最短路径。我从邻接矩阵中得到这些图。所以我要做的是从第一行（或第0行）开始，穿过这行，放松矩阵N中的顶点。然后从我存储在顶点存储中的任何顶点中找到最小的边，然后继续添加顶点，放松边。然后我有两个主要的数组，称为N（我存储最短路径的权重）和edgeStorage。下面是它的样子：

static int ShortestPath(int[][] G){
    int numVerts = G.length;
    int totalWeight = 0;

    int minWeight;
    int count = 1;
    int k = 0;
    int l = 0;
    int next = 1;
    int i = 0;
    int[] N = new int[numVerts];
    int[] edgeStorage = new int[numVerts];
    Arrays.fill(N, 2147483647); //2147483647 is my infinity to represent vertices that haven't yet been relaxed
    N[0] = 0;

    while (count != numVerts){
        for (int j = 0; j < numVerts; j++){
            if ((G[i][j] != 0) && (N[i] + G[i][j] < N[j])){
                N[j] = N[i] + G[i][j];
            }
        }
        minWeight = 2147483647;
        for (int p = 0; p < count; p++){ //find min edge weight for vertices in storage
            i = edgeStorage[p];
            for (int j = 0; j < numVerts; j++){
                if ((G[i][j] != 0) && (G[i][j] < minWeight)){
                    minWeight = G[i][j];
                    k = j;
                    l = i;
                }
            }
        }
        G[l][k] = 0; //remove edge since we don't need it anymore
        G[k][l] = 0;
        edgeStorage[next] = k; //store vertex location in array
        i = k;
        count++;
        next++;
    }
    totalWeight = N[1];
    return totalWeight;
}

问题是，这段代码适用于某些图形，但对于其他图形，它给了我一个比预期更大的权重。我在一个包含25个顶点的图上进行了测试，结果如下：

0 0 0 0 0 0 418 0 0 0 0 0 0 0 472 0 0 0 0 0 0 0 0 537 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 191 375 161 0
0 0 0 0 0 0 0 0 0 0 0 0 108 0 0 0 512 0 311 0 0 0 0 0 0
0 0 0 0 0 0 0 0 612 0 0 0 0 0 0 0 0 0 0 0 583 0 0 0 0
0 0 0 0 0 0 365 0 0 0 0 0 0 0 0 262 243 0 0 0 0 617 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 581 0 0 0 0 0 0 0 0 0 0 0
418 0 0 0 365 0 0 0 0 0 0 338 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 320 0 517 0 0 0 0 0 0 0 524 0 314 0 0 0 0
0 0 0 612 0 0 0 320 0 0 0 0 0 0 0 0 577 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 145 414 0 0 35 0 0 0 0 0 0 394 0 0
0 0 0 0 0 0 0 517 0 0 0 0 0 0 0 0 0 353 0 0 0 0 0 0 0
0 0 0 0 0 0 338 0 0 145 0 0 0 0 0 0 0 0 0 344 0 0 0 0 0
0 0 108 0 0 0 0 0 0 414 0 0 0 0 0 0 0 607 0 0 0 0 0 0 0
0 0 0 0 0 581 0 0 0 0 0 0 0 0 0 0 0 0 0 609 0 0 231 0 0
472 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 478 0 0 0 0 0 0 0
0 0 0 0 262 0 0 0 0 35 0 0 0 0 0 0 0 0 0 0 280 0 0 0 0
0 0 512 0 243 0 0 0 577 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 353 0 607 0 478 0 0 0 0 0 0 0 0 594 0
0 0 311 0 0 0 0 524 0 0 0 0 0 0 0 0 0 0 0 0 0 471 0 0 306
0 0 0 0 0 0 0 0 0 0 0 344 0 609 0 0 0 0 0 0 0 0 0 0 0
0 0 0 583 0 0 0 314 0 0 0 0 0 0 0 280 0 0 0 0 0 0 0 0 214
0 191 0 0 617 0 0 0 0 0 0 0 0 0 0 0 0 0 471 0 0 0 0 0 0
0 375 0 0 0 0 0 0 0 394 0 0 0 231 0 0 0 0 0 0 0 0 0 0 0
537 161 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 594 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 306 0 214 0 0 0 0

我的N数组如下所示：

0 1670 1538 1799 783 2107 418 1530 1603 901 2047 756 1315 1526 472 936 1026 950 1736 1100 1216 1400 1295 537 1430

我的edgeStorage阵列是这样的：

0 6 11 9 15 4 16 20 24 18 2 12 7 8 19 4 22 13 1 23 21 12 21 14 17

因此，它返回1670作为0和1之间的路径，而它本应返回698。我不知道为什么它给了我一些图表错误的权重，但给了其他图表正确的权重。有人知道我的代码出了什么问题吗

注：我知道我的实现目前不是最有效的，但我只想让基本的实现工作起来，然后我会努力提高效率