最短路径问题 弗洛依德Floyd算法：带权图中每一对顶点间最短路径

最短路径问题 弗洛依德Floyd算法：带权图中每一对顶点间最短路径"/>

最短路径问题 弗洛依德Floyd算法：带权图中每一对顶点间最短路径

A为存放图中所有顶点对之间的最短路径长度的n阶方阵。初始A为邻接矩阵，A=w。

取k=0,1，...，n-1，计算A[i][j]=min{A[i][j]，A[i][k]+A[k][j]}，（即vi到vj依次加入v0,v1,...vn-1，找最短路径）

P[n][n]，P[i][j]保存顶点i到j的最短路径中i的直接后继

例子，如下图，求下图的每个点对之间的最短路径的过程如下：

第一步，先初始化两个矩阵，得到下图两个矩阵： (矩阵中v1...v7改为v0...v6),

初始时，D为邻接矩阵

P矩阵中的0代表v0,1代表v1..........

第二步，以v0为中阶，更新两个矩阵： 
发现，w[1][0]+w[0][6] =12+14=26< w[1][6]=无穷 和w[6][0]+w[0][1] =14+12=26< a[6][1]=无穷，所以只需要矩阵D和矩阵P，结果如下：

通过上矩阵P，发现v1–v6的最短路径是：v1–v0–v6

第三步：以v1作为中介，来更新两个矩阵，使用同样的原理，扫描整个矩阵，得到如下图的结果：

w[0][1]+w[1][2]=12+10=22<w[0][2]=无穷，故修改D[0][2]=22，P[0][2]=1（路径v0-v2中，v0的后继为v1）

w[2][1]+w[1][6]=10+26=26<w[2][6]=无穷，故修改D[2][6]=36，P[2][6]=1（路径v2-v6中，v2的后继为v1）

通过上矩阵P发现，v0-v2的最短路径为v0-v1-v2，

v2-v6的最短路径为v2-v1-v0-v6（因为：路径v2-v6中，v2的后继为v1，而v1–v6的最短路径是v1–v0–v6）

第四步，以v2为中介，更新D和P：

每次都会选择一个中介点，然后，遍历整个矩阵，查找需要更新的值，下面还剩下4步，就不继续演示下去了，理解了方法，我们就可以写代码了。