Реализация алгоритма Дейкстры в Java?

Question

Поэтому я пытаюсь реализовать алгоритм Дейкстры в Java. Я знаю, что есть разные способы сделать это, но вот способ, которым я научился это делать. Поэтому я начинаю с одной вершины и нахожу кратчайший путь от этой вершины ко всем остальным вершинам. Я начинаю с одной вершины (в моем случае это ноль), а затем обновляю свою окрестность, ослабляя все ребра, связанные с этой вершиной. Затем я выясняю, какое наименьшее ребро соединяется с текущим ребром, и затем добавляю эту вершину в свое хранилище вершин. Я продолжаю делать это до тех пор, пока все вершины не будут в моем хранилище вершин, а затем я получу тип связующего дерева, который покажет мне все кратчайшие пути.

Поэтому в моем коде я пытаюсь найти кратчайший путь от 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. Я понятия не имею, почему он дает неправильный вес для одних графиков, но правильный вес для других. Так кто-нибудь знает, что не так с моим кодом?

PS: я знаю, что моя реализация сейчас не самая эффективная вещь, но я просто хочу, чтобы базовая реализация работала, и тогда я буду работать над тем, чтобы сделать ее более эффективной.