我们通常不是寻找单源最短路径[1]，而是在任意两个顶点（vi,vj）之间寻找最短路径。最快解决这个问题的方法是使用一个强有力的方法——动态规划。
动态规划有两个令人激动的特征：
·它专注解决较小的，有条件限制的问题。当限制条件很严格时，函数将会非常简单，系统地松弛限制条件，直到最后产生希望得到的结果。
·虽然我们希望为问题寻找到最优解，计算最优解的值比寻找什么是最优解要简单许多。在我们的例子中，计算每个点对（vi,vj）之间的最短距离，然后进行一些额外的计算得到实际的路径。
给定一个n×n的dist矩阵，我们计算得到，对于所有的顶点对（vi,vj）来说，dist[i][j]是vi到vj的最短路径。图6-18是Floyd-Warshall的伪代码，以及它在一个小例子上的执行过程。
图 6-18 Floyd-Warshall详解输入/输出
输入
一个有向有权图G=(V,E)。每条边e=(u,v)都有一个正权值。图G的顶点数为n。
输出
Floyd-Warshall算法得到一个矩阵dist，dist[u][v]的值表示从u到b的最短路径。注意如果dist[u][v]是∞，那么从u到v之间不存在路径。在两个顶点之间的实际路径可以从矩阵pred推导出来，当然，pred也是这个算法计算的结果。
假设
边的权值必须为正值（例如必须大于0）。
[1]可能有多条有相同长度的路径。