Floyd–Warshall算法简介

  Floyd–Warshall算法用于寻找有向图中任意两点间的最短路径,即多源最短路径。该算法可用于带负权边的图,但不能用于带负权环的图。该算法需要比较每一组节点间所有的路径,时间复杂度为Θ(|V|^3)。

  设有一个图G,有N个节点,编号为1,2,…,N。函数 shortestPath(i, j, k) 返回当仅使用点集{1,2,…,k}为中间节点时,从节点i到达节点j的最短距离。使用w(i, j)表示i和j之间边的权值,则对于节点(i, j)之间的最短路径,有两种情况:

(1)最短路径是从节点i直接到节点j,则有:

(2)最短路径是从节点i,经过非空节点集{1, 2, …, k}中的某些点作为中间节点,到达节点j。此情况又可以根据最短路径是否经过节点k,来继续分解求以下两条路径中较短的那一条:

  • 不经过节点k时,从i到j的最短距离即为 shortestPath(i, j, k - 1) ;
  • 经过节点k时,从i到j的最短距离是从i到k的最短距离加上从j到k的最短距离,即 shortestPath(i, k, k) + shortestPath(k, j, k) 。

则(2)中从i到j的最短路径即为 shortestPath(i, j, k - 1) 和 shortestPath(i, k, k) + shortestPath(k, j, k) 中较短的那一条,即:

  由此计算 shortestPath(i, j, N) ,即为任意两点(i, j)间的最短距离。Wiki给出了算法的伪代码如下: