[数据结构与算法]弗洛伊德（Floyd）算法（解决任意两点间的最短路径）

用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）。

    //Floyd算法求解任意两个顶点的最短距离问题，也就是多源最短路径问题
    public void floyd() {
    	//存储最短路径
    	int[][] dist=new int[vertex.length][vertex.length];
    	//记录最短路径经过的顶点
    	int[][] prev=new int[vertex.length][vertex.length];
    	//初始化
    	for(int i=0;i<vertex.length;i++) {
    		for(int j=0;j<vertex.length;j++) {
    			dist[i][j]=getWeight(i, j);  //存储的是权值
    			prev[i][j]=j;   //i到j一定会经过j
    		}
    	}
    	//三重循环，最外层的是顶点的个数，中间两层是遍历整个矩阵
    	//思想是：当k=0时，就借助于第k个顶点，如果i到j的距离可以变小，则更新最小距离
    	//其实就是借助于前k个顶点，如果i到j的距离可以变小，则更新最小距离
    	for(int k=0;k<vertex.length;k++) {
    		for(int i=0;i<vertex.length;i++) {
    			for(int j=0;j<vertex.length;j++) {
                    // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和prev[i][j]
                    int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                    if (dist[i][j] > tmp) {
                        // "i到j最短路径"对应的值,设为更小的一个(即经过k)
                        dist[i][j] = tmp;
                        // "i到j最短路径"对应的路径，经过k
                        prev[i][j] = prev[i][k];
                    }
    			}
    		}
    	}
    	
    	// 打印floyd最短路径的结果
        System.out.printf("floyd: \n");
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++)
                System.out.printf("%2d  ", dist[i][j]);
            System.out.printf("\n");
        }
    }