状态转移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i<k<j
思路对于每一个k(i<k<j)，全部遍历下来之后，肯定会发生一次有效的比较
public class FloydTest { private static int[][] matrix; private static int[][] path; public static void main(String[] args) { initMatrixAndPath( new int[][]{ {0, 1, 8, 5}, {1, 0, 7, 6}, {8, 7, 0, 2}, {5, 6, 2, 0}} ); floyd(matrix, path); printShortDistance(); printShortDistanceDetail(); } private static void initMatrixAndPath(int[][] matrix) { FloydTest.matrix = matrix; FloydTest.path = new int[matrix.length][matrix.length]; for (int i = 0; i < FloydTest.matrix.length; i++) { for (int j = 0; j < FloydTest.matrix[i].length; j++) { path[i][j] = j; } } } private static void floyd(int[][] matrix, int[][] path) { for (int k = 0; k < matrix.length; k++) { for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix.length; j++) { if (matrix[i][j] > matrix[i][k] + matrix[k][j]) { matrix[i][j] = matrix[i][k] + matrix[k][j]; path[i][j] = path[i][k]; } } } } private static String getNodeName(int nodeIndex) { return "v" + nodeIndex; } private static void printShortDistanceDetail() { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { int x = j; StringBuilder sb = new StringBuilder("最短路径[v" + i + ",v" + j + "]为:"); sb.append(getNodeName(x)); sb.append("<--"); while (path[i][j] != x) { x = path[i][x]; sb.append(getNodeName(path[i][x])); sb.append("<--"); } sb.append(getNodeName(i)); System.out.println(sb); } } } private static void printShortDistance() { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { System.out.println("v" + i + "到" + "v" + j + "最短路径为:" + matrix[i][j]); } } }}输出结果
v0到v0最短路径为:0v0到v1最短路径为:1v0到v2最短路径为:7v0到v3最短路径为:5v1到v0最短路径为:1v1到v1最短路径为:0v1到v2最短路径为:7v1到v3最短路径为:6v2到v0最短路径为:7v2到v1最短路径为:7v2到v2最短路径为:0v2到v3最短路径为:2v3到v0最短路径为:5v3到v1最短路径为:6v3到v2最短路径为:2v3到v3最短路径为:0最短路径[v0,v0]为:v0<--v0最短路径[v0,v1]为:v1<--v0最短路径[v0,v2]为:v2<--v3<--v0最短路径[v0,v3]为:v3<--v0最短路径[v1,v0]为:v0<--v1最短路径[v1,v1]为:v1<--v1最短路径[v1,v2]为:v2<--v1最短路径[v1,v3]为:v3<--v1最短路径[v2,v0]为:v0<--v3<--v2最短路径[v2,v1]为:v1<--v2最短路径[v2,v2]为:v2<--v2最短路径[v2,v3]为:v3<--v2最短路径[v3,v0]为:v0<--v3最短路径[v3,v1]为:v1<--v3最短路径[v3,v2]为:v2<--v3最短路径[v3,v3]为:v3<--v3其他：看了网上的一些关于floyd算法证明的过程。其实最主要的一点，证明求d(i,k)+d(k,j)时，d(i,k)和d(k,j)已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。