在Java中实现Dijkstra的算法？-Java 学习之路

所以我试图在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时 . 我不知道为什么它给了我一些图的错误权重，但对其他图表权重 . 那么有谁知道我的代码有什么问题？

P.S：我知道我的实现现在不是最有效的，但我只想让基本实现工作，然后我会努力提高它的效率 .

在Java中实现Dijkstra的算法？

相关问题