Floyd–Warshall算法简介

Author: 2015-08-30

ACM

, ,

　　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，则有：

shortestPath(i, j, 0) = w(i, j)
shortestPath(i, j, 0) = w(i, j)
shortestPath(i, j, 0) = w(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, k) = min(shortestPath(i, j, k - 1), shortestPath(i, k, k) + shortestPath(k, j, k))
shortestPath(i, j, k) = min(shortestPath(i, j, k - 1), shortestPath(i, k, k) + shortestPath(k, j, k))
shortestPath(i, j, k) = min(shortestPath(i, j, k - 1), shortestPath(i, k, k) + shortestPath(k, j, k))

　　由此计算shortestPath(i, j, N) ，即为任意两点(i, j)间的最短距离。Wiki给出了算法的伪代码如下：
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) // the weight of the edge (u,v) for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
	dist[v][v] ← 0
for each edge (u,v)
	dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
	for i from 1 to |V|
		for j from 1 to |V|
			if dist[i][j] > dist[i][k] + dist[k][j] 
				dist[i][j] ← dist[i][k] + dist[k][j]
			end if