关于给出的n个顶点有向图，这里给出一个含有6个顶点的有向图，如下所示
Floyd又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法，其基本思想是：
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
首先考虑路径(vi,v0,vj)是否存在，如果存在，则在(vi,vj)和(vi,v0,vj)之间取路径最短者。在该路径上在增加一个顶点v1，若(vi....v1)和(v1...vj)是当前找到的中间点序号不大于0的最短路径，则(vi,....v1....vj)就有可能是从vi到vj的中间点序号不大于0的最短路径，将它和已经得到从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出长度较短者作为从vi到vj中间点序号不大于1的最短路径之后，再增加一个顶点从v2继续进行试探，以此类推，最后求得的必然是从vi到vj的最短路径。
算法具体实现如下：
package 有向网每对顶点的路径Floyd算法; import java.util.ArrayList; /** * @author wangyq * @date 2016-07-10 15:20 */ public class Floyd { /* * 给出一个含有n个顶点的带权有向图，要求其每一对顶点之间的最短路径。 * 这里采用佛洛依德(Floyd)最短路径算法： */ private static int max=Integer.MAX_VALUE; private static int [][]dist=new int[6][6]; //存储最短路径 private static int [][]path=new int[6][6]; //存储最短路径的长度 private static ArrayList list=new ArrayList (); private static int [][]Arcs={ {max,max,10,max,30,100}, {max,max,5,max,max,max}, {max,max,max,50,max,max}, {max,max,max,max,20,10}, {max,max,max,max,max,60}, {max,max,max,max,max,max} }; public void findCheapestPath(int begin,int end,int Arcs[][]){ floyd(Arcs); list.clear(); list.add(begin); findPath(begin,end); list.add(end); } public void findPath(int i,int j){ int k=path[i][j]; if(k==-1) return ; findPath(i,k); list.add(k); findPath(k,j); } public void floyd(int [][] Arcs){ int n=Arcs.length; for(int i=0;i L=f.list; System.out.print(i+"-->"+j+":"); if(f.dist[i][j]==max){ System.out.println("之间没有最短路径"); System.out.println(); } else{ System.out.println("的最短路径是："); System.out.print(L.toString()+" "); System.out.println("路径长度:"+f.dist[i][j]); System.out.println(); } } } } 调试结果如下：
