弗洛伊德Warshall算法實現

我寫的代碼，表示以下有向圖100×100鄰接矩陣：弗洛伊德Warshall算法實現

我試圖用弗洛伊德 - Warshall算法找到最短圖中所有藍色節點對的路徑。你如何才能找到所選節點的所有配對最短路徑？下面是我迄今爲止編寫的代碼：

public class AdjacencyMatrix 
 
{  
 
    public static final int NUM_NODES = 100; 
 
    public static final int INF = Integer.MAX_VALUE; 
 
    
 
    public static boolean even(int num) 
 
    { 
 
     return num%2==0; 
 
    } 
 

 
    public static boolean odd(int num) 
 
    { 
 
     return num%2==1; 
 
    } 
 

 
    public static void initialize(int [][] adjMat, int N) 
 
    { 
 
     for(int i = 0; i < N; i++) 
 
      for(int j = 0; j <N; j++) 
 
       adjMat[i][j]=INF; 
 

 
     for(int x = 0; x<N; x++) 
 
     { 
 
      int row = x/10; 
 
      int column = x%10; 
 

 
      if (even(row)) { 
 
       if (column!=9) 
 
        adjMat[x][x+1]=1; 
 
      } 
 
      if (odd(row)) { 
 
       if (column!=0) 
 
        adjMat[x][x-1]=1; 
 
      } 
 
      if (even(column)){ 
 
       if (row!=9) 
 
        adjMat[x][x+10]=1; 
 
      } 
 
      if (odd(column)) { 
 
       if (row!=0) 
 
        adjMat[x][x-10]=1; 
 
      } 
 
     } 
 
    } 
 
    
 
    public void floydWarshall(int[][] adjMat, int N) 
 
    { 
 
    \t adjMat = new int[N][N]; 
 
\t  initialize(adjMat, NUM_NODES); 
 

 
     for(int k = 0; k < N; ++k) { 
 
      for(int i = 0; i < N; ++i) { 
 
       for(int j = 0; j < N; ++j) { 
 
       adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
 
    } 
 
} 
 
} 
 

 
    } 
 

 
    public static void main(String[] args) 
 
    { 
 

 
     int adjMat[][] = new int[NUM_NODES][NUM_NODES]; 
 
     initialize(adjMat, NUM_NODES); 
 
     
 
     int A,B,C,D,E,F,G,H,I,W; 
 
     
 
     A = 20; 
 
     B = 18; 
 
     C = 47; 
 
     D = 44; 
 
     E = 53; 
 
     F = 67; 
 
     G = 95; 
 
     H = 93; 
 
     I = 88; 
 
     W = 66; 
 
     
 
     System.out.println(adjMat[A][B]); 
 

 
     System.out.println(); 
 
    } 
 
}

來源

2017-03-05 Nate

它看起來並不像你解開任何東西。 – Nate

最短弗洛伊德 - 沃肖爾算法中實行：

for(int k = 0; k < N; ++k) { 
    for(int i = 0; i < N; ++i) { 
     for(int j = 0; j < N; ++j) { 
      adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
     } 
    } 
}

運行這塊凱德後adjMat將包含每一個之間的最短距離節點對。

更新：爲避免整數溢出，使用Integer.MAX_VALUE/2填充矩陣。在一般情況下，將最大可能值設置爲無窮大是很危險的，因爲您無法對其執行附加操作。

來源

2017-03-05 22:44:27 Andreikkaa

我已經將你的代碼添加到了floydWarshall（）方法中，但是它輸出了所有0的矩陣。 – Nate

我還沒有得到這個代碼輸出正確。它看起來像邏輯是正確的，所以我不知道發生了什麼問題。 – Nate

我對java不熟悉，但是如果一個術語是Intmax，會adjMat [i] [k] + adjMat [k] [j]溢出嗎？ –

首先，您不應該爲floydWarshall（）中的adjMat參數指定新值，因爲在退出該方法後該值不會被保存。

下一個步驟是檢查adjMat [I] [k]和adjMat [K] [j]的平等到INF，然後繼續循環，如果這樣：

for(int k = 0; k < N; ++k) { 
    for(int i = 0; i < N; ++i) { 
     for(int j = 0; j < N; ++j) { 
     if (adjMat[i][k] != INF && adjMat[k][j] != INF) { 
      adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
     }

來源

2017-03-06 19:14:59 Nolequen

弗洛伊德Warshall算法實現

回答

相關問題