java實現Floyd算法的示例

這篇文章給大家分享的是有關java實現Floyd算法的示例的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

Floyd算法:用于多源最短路徑的求解，算出來的是所有的節點到其余各節點之間的最短距離。

該算法的思路是：首先初始化距離矩陣，然后從第一個點開始逐漸更新矩陣點值。d[i][j]表示從i點到j點的距離。第k次更新時，判斷d[i][k]+d[k][j]與d[i][j]的大小，如果前者小，則更新這個值，否則不變。

給一個例子：

具體的floyd實現算法如下[java] view plain copy

package com.blyang; 
 
public class Floyd { 
   
  int[][] Matrix; 
  char[] Nodes; 
   
  private final int INF = Integer.MAX_VALUE; 
   
  public Floyd(char[] Nodes, int[][] Matrix){ 
    this.Nodes = Nodes; 
    this.Matrix = Matrix; 
  } 
   
  public void floyd(){ 
     
    int[][] distance = new int[Nodes.length][Nodes.length]; 
     
    // 初始化距離矩陣 
    for(int i=0; i<Nodes.length; i++){ 
      for(int j=0; j<Nodes.length; j++){ 
        distance[i][j] = Matrix[i][j]; 
      } 
    } 
     
    //循環更新矩陣的值 
    for(int k=0; k<Nodes.length; k++){ 
      for(int i=0; i<Nodes.length; i++){ 
        for(int j=0; j<Nodes.length; j++){ 
          int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j]; 
          if(distance[i][j] > temp){ 
            distance[i][j] = temp; 
          } 
        } 
      } 
    } 
     
    // 打印floyd最短路徑的結果 
    System.out.printf("floyd: \n"); 
    for (int i = 0; i < Nodes.length; i++) { 
      for (int j = 0; j < Nodes.length; j++) 
        System.out.printf("%12d ", distance[i][j]); 
      System.out.printf("\n"); 
    } 
  } 
}

在實現之后，針對上圖的點和權值，給定一個測試：

package com.blyang; 
 
public class Main { 
 
 
   
  public static void main(String[] args) { 
    int INF = Integer.MAX_VALUE; 
     
    char[] Nodes = {'0', '1', '2', '3'}; 
    int matrix[][] = { 
         /*A*//*B*//*C*//*D*/ 
     /*A*/ {  0,  1,  2,  1}, 
     /*B*/ { INF,  0, INF, INF}, 
     /*C*/ { INF,  3,  0,  1}, 
     /*D*/ { INF,  1,  1,  0}, 
     }; 
       
    int[] dist = new int[Nodes.length]; 
   
    Floyd floyd = new Floyd(Nodes, matrix); 
    floyd.floyd(); 
 
  } 
   
}

感謝各位的閱讀！關于“java實現Floyd算法的示例”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！