最短路徑Dijkstra Java

Question

我想用dijktra的算法打印一個特定的鄰接矩陣的最短路徑。我的dijkstra算法工作正常，我得到正確的距離。但是，當打印出路徑時，我得到的路徑不正確。這裏是我打印路徑的代碼：

我的第一堂課是我的驅動程序，它採用了一個鄰接矩陣。矩陣包含文件頂部的大小，中間的實際矩陣以及文件末尾的源頂點。這一切都適用於計算最短距離。以下是我的完整代碼。

public void findPath(int size, int s) { 

    // print the path and the distance of each vertex 

    int j; 
    // iterate to find the distances 
    for (int i = 0; i < size; i++) { 
     System.out.print("[" + distance[i] + "] "); 

     if (i != 0) { 

      System.out.print(s); 
      j = i; 
      do { 

       j = path[j]; 
       System.out.print(" <- " + j); 

      } while (j != startVertex); 

     } 

     System.out.println(); 

    } 

} 
} 

Answer 1

您的findPath方法存在以下問題：

1. 你無故與if (i != 0)跳行輸出。
2. 您的數據是基於0的索引的形式，並且您的期望輸出是基於1的，並且您不在它們之間進行轉換。
3. 您正在以您想要的相反順序輸出數據，當您的預期輸出將起始點放在最後時，首先打印路徑的起點。
4. 通過在打印任何內容之前遵循路徑中的一個步驟，您將跳過路徑的第一步。
5. 通過使用do循環而不是while，您正在打印虛假的「通過靜止移動」路徑步驟來獲取短路徑。

我沒有檢查你的Dijkstra邏輯不多，但結合這些錯誤將改變你的預期輸出相匹配到觀察到輸出路徑數據，所以我認爲你是正確的，Dijkstra算法是否正常工作。

修復其中大部分應該是微不足道的，但修復錯誤＃3將需要一個小的算法改變 - 在輸出任何它之前跟蹤和反轉路徑。

爲了更清楚，這裏是你的原代碼標記所有固定點：

public void findPath(int size, int s) { 

    // print the path and the distance of each vertex 

    int j; 
    // iterate to find the distances 
    for (int i = 0; i < size; i++) { 
     System.out.print("[" + distance[i] + "] "); 

     // FIX #1: Remove this if statement 
     if (i != 0) { 

      System.out.print(s); 
      j = i; 
      // FIX #5: Use while instead of do 
      do { 

       // FIX #4: swap the order of these two lines 
       j = path[j]; 
       // FIX #2: print j+1, not j 
       // FIX #3: Instead of print, push onto a stack 
       System.out.print(" <- " + j); 

      } while (j != startVertex); 

      // FIX #3: Put your pop-and-print loop here. It should not 
      // involve i, and should end when the stack is empty, not 
      // any other condition. 
     } 

     System.out.println(); 

     } 
    } 
}