Dijkstra算法輔助

Question

給定一個鄰接矩陣，我需要計算第一個頂點和最後一個頂點之間的最短路徑（通常是頂點i和j，但我們暫時可以忽略）。我寫了一個算法，它只能正確地計算第一個和第二個節點之間的距離（我猜是朝着正確的方向邁出了一步）。

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之間的一條路徑）。

Answer 1

如果矩陣不只是存儲1s和0s，而是存儲從i到j的距離，那麼您確實需要跟蹤從任何節點i到j的最佳距離。換句話說，你的工作陣列應該是一個工作矩陣。即使你只是做一個非加權圖，我認爲這種方法更好。

有不同版本的SPF算法。爲你想要翻譯成java的文章發佈僞代碼。