任意两点间最短路（Floyd）

多有点对的最短路，Floyd 算法 InPut:n×n维矩阵l[1...n][1...n],对应于有向图G=（{1,2,...n},E） 中的边(i,j)的长度为l[i][j]. OutPut:矩阵D,D[i,j]等于i到j的最短距离。

public class Floyd{ private static final int NaN = 9999; public static void main(String[] args){ int[][] L = {​{0,2,9},{8,0,6},{1,NaN,6}}; int[][] D = new int[3][]; int n = 3; System.arraycopy (L,0,D,0,L.length); for(int k=0; k<n; k++){ for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ D[i][j] = min(D[i][j],D[i][k]+D[k][j]); } } } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ System.out.print(D[i][j]); } System.out.println(); } } public static int min(int a, int b){ return a < b ? a : b; } }