java实现佛洛依德算法

所用到的测试图：

package algorithm;

/
 * 弗洛伊德算法思想:
 * 	Ak(i,j)意思是i点到j点经过一系列点，但是点下标最多不超过k
 * 情况1：如果Ak(i,j)不经过k,那么Ak(i,j)=Ak-1(i,j);
 * 情况2：如果Ak(i,j)经过k，那么Ak(i,j)=Ak-1(i,k)+Ak-1(k,j);
 * 	所以Ak(i,j) = min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)};
 * 
 * 第k层的计算依赖于k-1的结果，所以循环从k=0开始计算起
 *
 */
public class FloydAlgorithm {
	private int[][] matrix;  // 用邻接矩阵来表示图
    private char[]  nodeNames;  // 每个点的标号对应一个字符，代表点的名字
    private final int INF = Integer.MAX_VALUE;  
    public FloydAlgorithm(char[] nodeNames, int[][] matrix){  
        this.nodeNames = nodeNames;  
        this.matrix = matrix;  
    }  
    
    public void floyd(){ // 计算出任意两点间的最短路径，只要该路径存在
        int vertexNum = nodeNames.length;
        int[][] distance = new int[vertexNum][vertexNum];// 距离矩阵  
        StringBuilder[][] path = new StringBuilder[vertexNum][vertexNum];//用来存储最短路径经过的点
        // 初始化距离矩阵  
        for(int i=0; i
   
  
   
   
   
   
   
     0代表该边存在 初始化它的路径 path[i][j].append(nodeNames[i]+"->"+nodeNames[j]); } } } //循环更新矩阵的值 最外层循环代表经过的点下标不超过k时的最短路径 for(int k=0; k 
    
      ak_1ik_plus_ak_1kj||ak_1ij==0?ak_1ik_plus_ak_1kj:ak_1ij;//比较求出最短ak(i,j) if(distance[i][j]==ak_1ik_plus_ak_1kj) { //处理路径字符串的拼接 path[i][j].delete(0,path.length+1).append(path[i][k].toString().substring(0, path[i][k].length()-1)+path[k][j].toString()); // 之前出现C->B:BC->D->B这种状况是因为之前的Stringbuilder没有清空导致的 } } } } } System.out.printf("原矩阵: \n"); for (int i = 0; i < vertexNum; i++) { for (int j = 0; j < vertexNum; j++) System.out.printf("%02d ",matrix[i][j]); System.out.printf("\n"); } // 打印floyd最短路径的结果 System.out.printf("最短距离矩阵: \n"); for (int i = 0; i < vertexNum; i++) { for (int j = 0; j < vertexNum; j++) System.out.printf("%02d ",distance[i][j]); System.out.printf("\n"); } System.out.printf("最短路径: \n"); for (int i = 0; i < vertexNum; i++) { for (int j = 0; j < vertexNum; j++) { if(i==j||distance[i][j]==0) continue; System.out.println(nodeNames[i]+"->"+nodeNames[j]+"的最短路径为: "+path[i][j]); } } } public static void main(String[] args) { long start = System.currentTimeMillis(); int[][] graph = new int[6][6]; char[] nodeNames = new char[] {'A','B','C','D','E','F'}; graph[0][1] = 50; graph[0][2] = 10; graph[0][4] = 45; graph[1][2] = 15; graph[1][4] = 10; graph[2][0] = 20; graph[2][3] = 15; graph[3][1] = 20; graph[3][4] = 35; graph[4][3] = 30; graph[5][3] = 3; FloydAlgorithm floydAlgorithm = new FloydAlgorithm(nodeNames, graph); floydAlgorithm.floyd(); long end = System.currentTimeMillis(); System.out.println("程序用时:"+(end-start)/1000.0+"秒"); } } 
     
   

输出结果：

原矩阵: 
00 50 10 00 45 00 
00 00 15 00 10 00 
20 00 00 15 00 00 
00 20 00 00 35 00 
00 00 00 30 00 00 
00 00 00 03 00 00 
最短距离矩阵: 
00 45 10 25 45 00 
35 00 15 30 10 00 
20 35 00 15 45 00 
55 20 35 00 30 00 
85 50 65 30 00 00 
58 23 38 03 33 00 
最短路径: 
A->B的最短路径为: A->C->D->B
A->C的最短路径为: A->C
A->D的最短路径为: A->C->D
A->E的最短路径为: A->E
B->A的最短路径为: B->C->A
B->C的最短路径为: B->C
B->D的最短路径为: B->C->D
B->E的最短路径为: B->E
C->A的最短路径为: C->A
C->B的最短路径为: C->D->B
C->D的最短路径为: C->D
C->E的最短路径为: C->D->B->E
D->A的最短路径为: D->B->C->A
D->B的最短路径为: D->B
D->C的最短路径为: D->B->C
D->E的最短路径为: D->B->E
E->A的最短路径为: E->D->B->C->A
E->B的最短路径为: E->D->B
E->C的最短路径为: E->D->B->C
E->D的最短路径为: E->D
F->A的最短路径为: F->D->B->C->A
F->B的最短路径为: F->D->B
F->C的最短路径为: F->D->B->C
F->D的最短路径为: F->D
F->E的最短路径为: F->D->B->E