floyd算法的例题讲解,floyd算法程序

Java实现诚心的香烟算法（floyd）的完整代码 /** * 弗洛伊德(floyd)算法求图中所有点对之间的最短路径； * 其中‘-1’表示两点之间目前还没有联通的路径； * 结论：如果A点到G点之间有最短路径，那么被这条最短路径所包含的所有点之间的最短路径一定是这条最短路径的子集（或子路段）。 */public int[][] floyd(int[][] initialGraph){int[][] resultGrapg=initialGraph.clone();//for(int[] i : resultGrapg) {//for(int j : i) System.out.print(" "+j+",");//System.out.println();//}// 加的点要写在最外层，因为写在内层的话，所加的点在i，j（如：1，2）两点间的路径是不能叠加的，而在最外层才能叠加增加的点// 因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个k，// 每加一个中间点，即计算出加该点后，所有因为加该点而变短的 “所有路径”。for(int k=0; k<resultGrapg[0].length; k++) { for(int i=0; i<resultGrapg[0].length; i++) {for(int j=0; j<resultGrapg[0].length; j++) {if(resultGrapg[i][j]>resultGrapg[i][k]+resultGrapg[k][j]) {resultGrapg[i][j]=resultGrapg[i][k]+resultGrapg[k][j];}}}}//System.out.println("r==================r");//for(int[] i : resultGrapg) {//for(int j : i) System.out.print(" "+j+",");//System.out.println();//}return resultGrapg;}