介绍弗洛伊德(Floyd )算法和Dijkstra算法一样，弗洛伊德(Floyd )算法也是一种用于在给定加权图中查找顶点之间最短路径的算法。 该算法名称来源于创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授冷静的铃铛： http://www.Sina.com/http://www.Sina.com /弗洛伊德算法VS 弗洛伊德的算法中各顶点为出发点访问点，因此有必要将各顶点视为被访问顶点，求出从各顶点到其他顶点的最短路径。 弗洛伊德(Floyd )算法图解分析中，如果将从顶点vi到顶点vk的最短路径设为Lik，将从顶点vk到vj的最短路径设为Lkj，将从顶点vi到vj的路径设为Lij，则从vi到vj的最短路径为min ()、Lij ) 得到从vi到vj的最短路径。 对于从vi到vk的最短路径Lik或从vk到vj的最短路径Lkj，也同样得到弗洛伊德(Floyd )算法的图解分析。 例：说明求出最短路径的例子
弗洛伊德算法步骤：
在第一个循环中，当遍历以a (下标：0)为中间顶点的【即以a为中间顶点的所有情况时，距离表和前驱关系被更新】，距离表和前驱关系被更新如下。
分析如下。
将a顶点作为中间顶点是因为B-A-C距离为N-9，同样地从c到b； C-A-G的距离为N-12，同样地从g向c更换中间顶点，反复进行操作直到所有顶点作为中间顶点被更新之后，计算结束中间顶点[A、b、c、d、e、f、G]
出发顶点[A、b、c、d、e、f、G]
终点[A，b，c，d，e，f，G]
弗洛伊德算法的最优应用——最短路径
胜利乡有7个村庄(a、b、c、d、e、f、g )，用分界线表示每个村庄的距离。 例如，Ab相距5公里。 怎么计算各村到其他村的最短距离？ 代码实现import java.util.Arrays； 测试是否成功创建了publicclassfloydalgorithm { publicstaticvoidmain (字符串) args )//图。 char ) ) vertex={'a '、' b '、' c '、'//邻接矩阵int [ ] [ ]矩阵=new int [ vertex.length ] [ vertex.length ]； final int N=65535； matrix [0]=new int [ ] { 0，5，7，n，n，n，2 }； matrix [1]=new int [ ] { 5，0，n，9，n，n，3 }； matrix[2]=new int[] { 7，n，0，n，8，n，N }； matrix[3]=new int[] { N，9，n，0，n，4，N }； matrix[4]=new int[] { N，n，8，n，0，5，4 }； matrix[5]=new int[] { N，n，n，4，5，0，6 }； matrix [6]=new int [ ] { 2，3，n，n，4，6，0 }； 创建图形对象graph graph=new graph (Vertex.length，matrix，vertex )； //调用弗洛伊德算法graph.floyd (； graph.show (； }//class graph { private char [ ] vertex； //存储顶点的数组private int[][] dis； //保存、每个顶点到其他顶点的距离、最后的结果也是此数组private int[][] pre； //到达目标顶点的前驱顶点//构造函数/** * * @param length *大小* @ param矩阵* @param vertex *顶点数组*/public graph (int llix ) this.pre=new int [ length ] [ length ]； //pre数组初始化，前体顶点下标for(intI=0； i length； I ) {Arrays.fill(pre[I]，I )； }//pre和dis数组的public void show () /输出char[] vertex={ 'A '、' b '、' c '、' d '、' e '、' f '和' g '，以方便阅读k dis.length； k () /先将pre数组输出的一行设置为for(intI=0； i dis.length； I ) system.out.print (vertex [ pre [ k ] [ I ] ' )； }System.out.println (； 输出//dis阵列的一行数据for (inti=0； i dis.length； I ) ) system.out.print (() ) vertex[i] )到) vertex[i] () ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。 }System.out.println (； System.out.println (； (//Flood算法简单易懂，且易于实现公共语音流量) ({int len=0)。 //变量保存距离//遍历中间顶点，k是中间顶点的下标[A，b，c，d，e，f，g]for(intk=0； k dis.length； (k )从///I的顶点开始[A，b，c，d，e，f，g]for(intI=0； i dis.length； I ) )到达//j的顶点((a，b，c，d，e，f，g ) for(intj=0； j dis.length； j () {len=dis[i][k] dis[k][j]； 如果从//I顶点出发，经过k中间顶点，到j顶点的距离if(lendis[I][j] ) len小于dis [ I ] dis [ I ] [ j ]=len )，则为//更新距离pre [ I ] //更新前驱顶点}}}}}}