floyd算法的原理

一条最短路径的所有子路径也是最短路径。因此,从顶点i到顶点j的最短路径:

floyd-theory.png
假设i到j的最短路径需要经过若干个顶点来中转,k是这些中转节点中的索引值最大的那个顶点,根据前面的性质,可以得到:

对于任意k(1 <= k <= n):
当 k = 0时,意味着没有中间节点来中转,则D[k][i][j] = Weight[i][j]
否则,存在两种情况:

因此D[k][i][j] = MIN(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])
可以看出floyd算法本质上就是一个动态规划。
同时,可以设置两个辅助数组D[][] 和 P[][],其中D[i][j]用来保存从i到j的最短路径,初始时,任意两个顶点之间的最短路径都是INFINITY。P[i][j]用来保存从i到j所需经过的中继顶点,初始时,P[x][j] = j。对于已经计算出最短路径的两个顶点,可以直接从D[i][j]取值,这样可以防止重复计算,提高动态规划的执行效率。P[][]主要用来追踪最短路径。


Java实现

tim-chow的github