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(); 
 
  } 
   
} 

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。