0

隣接行列が与えられた場合、最初の頂点と最後の頂点の間の最短経路を計算する必要があります（通常、頂点iとjですが、当面は無視できます）。私は、最初のノードと2番目のノードの間の距離を実際に正しく計算するだけのアルゴリズムを作成しました（正しい方向へのステップだと思います）。

static int dijkstra(int[][] G, int i, int j) {
    //Get the number of vertices in G
    int n = G.length;
    int[] bestpath = new int[n];
    int max = Integer.MAX_VALUE;
    boolean[] visited = new boolean[n];

    for (int x = 0; x < n; x++) {
        visited[x] = false;
        bestpath[x] = max;
    }

    bestpath[i] = 0;

    for (int x = 0; x < n; x++) {
        int min = max;
        int currentNode = i;
        for (int y = 0; y < n; y++) {
            if (!visited[y] && bestpath[y] < min) {
                System.out.println(G[y][x]);
                currentNode = y;
                min = bestpath[y];
            }
        }
        visited[currentNode] = true;
        for (int y = 0; y < n; y++) {
            if (G[currentNode][y] < max && bestpath[currentNode] + G[currentNode][y] < bestpath[y]) {
                bestpath[y] = bestpath[currentNode] + G[currentNode][y];
            }
        }
    }

    return bestpath[j];
}

私が推測すると、このセクションでは私の論理に欠陥があると思います。

 for (int y = 0; y < n; y++) {
            if (!visited[y] && bestpath[y] < min) {
                System.out.println(G[y][x]);
                currentNode = y;
                min = bestpath[y];
            }
 }

例はマトリックスです

0 1 0 
1 0 1
0 1 0

これは2を返します（重み1の頂点1と2の間のパスと、重み1の2と3の間のパス）。

4

1 に答える 1

0

行列が 1 と 0 だけでなく、i から j までの距離を格納している場合、任意のノード i から j までの最適な距離を追跡する必要があります。つまり、作業配列は代わりに作業行列にする必要があります。重み付けされていないグラフを実行しているだけでも、このアプローチの方が優れていると思います。

SPF アルゴリズムにはさまざまなバージョンがあります。Java に変換しようとしているものの擬似コードを投稿します。

于 2012-12-03T02:52:51.133 に答える