變形最短路徑算法（路線從一個節點至自身）

的本人申請的所有點對最短路徑算法（Floyd-Warshall）到這個有向圖： alt text http://www.freeimagehosting.net/uploads/99b00085bf.jpg 變形最短路徑算法（路線從一個節點至自身）

該圖是由它的鄰接矩陣來表示。簡單的代碼如下所示：

public class ShortestPath { 

public static void main(String[] args) { 
    int x = Integer.MAX_VALUE; 
    int [][] adj= {  
     {0, 6, x, 6, 7}, 
      {x, 0, 5, x, x}, 
      {x, x, 0, 9, 3}, 
      {x, x, 9, 0, 7}, 
      {x, 4, x, x, 0}}; 

    int [][] D = adj; 

    for (int k=0; k<5; k++){ 
     for (int i=0; i<5; i++){ 
      for (int j=0; j<5; j++){ 
       if(D[i][k] != x && D[k][j] != x && D[i][k]+D[k][j] < D[i][j]){ 
         D[i][j] = D[i][k]+D[k][j];      
        } 
      } 
     }  
    } 

    //Print out the paths 
    for (int r=0; r<5; r++) { 
     for (int c=0; c<5; c++) { 
      if(D[r][c] == x){ 
       System.out.print("n/a"); 
      }else{ 
      System.out.print(" " + D[r][c]); 
      } 
     } 
     System.out.println(" "); 
    } 
}

}

以上工作正常，至於算法而言。

我試圖表明，從任何節點本身的路徑是不一定0，利用這裏的鄰接矩陣所暗示的，但可以通過其他節點的任何可能的路徑：例如B -...-...-...-B

有沒有辦法修改我當前的表示形式，以指示從B到B的最短路徑不是零，而是12，跟在B-C-E-B路徑後面？可以通過修改鄰接矩陣方法來完成嗎？

來源

2009-12-23 denchr

將對角元素鄰接矩陣從0改爲無窮（理論上）應該有效。

這意味着自我循環成本是無限的，任何其他路徑的成本都低於此成本，因此如果從節點到其自身，通過其他節點存在路徑，其成本將是有限的，它將取代無限值。

實際上，您可以使用整數的最大值作爲無限。

來源

2009-12-23 19:19:05 codaddict

+1該矩陣告訴算法，B-> B路徑的權重爲0，所以它當然是最短的。明確定義自身邊的權重以賦予它們權重。 :) – PSpeed 2009-12-23 19:27:52

非常感謝提示，其實很簡單。 – denchr 2009-12-23 19:56:20

變形最短路徑算法（路線從一個節點至自身）

回答

相關問題