package Algorithm;import java.util.Arrays;public class Floyd {public static void main(String[] args) {char [] vertex = {'A','B','C','D','E','F','G'};//顶点final int N = 65535;//邻接矩阵，N 表示不可达int [][] matrix = {{0,5,7,N,N,N,2},{5,0,N,9,N,N,3},{7,N,0,N,8,N,N},{N,9,N,0,N,4,N},{N,N,8,N,0,5,4},{N,N,N,4,5,0,6},{2,3,N,N,4,6,0}};//测试FGraph fGraph = new FGraph(vertex,matrix);fGraph.floyd();fGraph.show(vertex);}}//图class FGraph{private char [] vertex;//顶点的数组private int [][] dis;//各个顶点到各顶点的距离数组private int [][] pre;//顶点的前驱数组//构造public FGraph(char [] vertex, int [][] matrix){this.vertex = vertex;this.dis = matrix;//各个顶点到各顶点的距离数组 初始化为邻接矩阵//初始化前驱数组pre = new int[vertex.length][vertex.length];for(int i = 0; i < vertex.length; i++){Arrays.fill(pre[i],i);}}public void floyd(){int len;//记录中间距离//遍历中间顶点for(int k = 0; k < vertex.length; k++){//遍历出发顶点for(int i = 0; i < vertex.length; i ++){//遍历终点for(int j = 0; j < vertex.length; j++){len = dis[i][k] + dis[k][j];//i 到 j 经过顶点 k 的距离if(len < dis[i][j]){dis[i][j] = len;//更新距离pre[i][j] = pre [k][j];//更新前驱}}}}}//显示结果，dis 和 prepublic void show(char [] vertex){for(int i = 0; i < vertex.length; i++){//显示一行prefor(int j = 0; j < vertex.length; j++){System.out.print(vertex[ pre[i][j] ] + " ");}System.out.println();//显示一行disfor(int j = 0; j < vertex.length; j++){System.out.print(vertex[i] + "--" + vertex[j] + "的 dis = " + dis[i][j] + " ");}System.out.println();System.out.println();}}}
如果觉得《佛洛依德算法求各个结点到各个结点的最短路径》对你有帮助，请点赞、收藏，并留下你的观点哦！
