Floyd-Warshall算法

维基百科,自由的百科全书
(重定向自弗洛伊德算法
跳转至: 导航搜索
Floyd-Warshall算法
分類 全局最短路径问题(适用于带权图)
數據結構
最差時間複雜度 O(|V|^3)
最優時間複雜度 \Omega (|V|^3)
最差空間複雜度 \Theta(|V|^2)

Floyd-Warshall算法英语Floyd-Warshall algorithm),中文亦称弗洛伊德算法,是解决任意两点间的最短路径的一种算法[1],可以正確處理有向圖或负权的最短路径問題,同时也被用于计算有向图的传递闭包[2]

Floyd-Warshall算法的时间复杂度O(N^3)[3]空间复杂度O(N^2)

原理[编辑]

Floyd-Warshall算法的原理是动态规划[4]

D_{i,j,k}为从ij的只以(1..k)集合中的节点为中间節点的最短路径的长度。

  1. 若最短路径经过点k,则D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}
  2. 若最短路径不经过点k,则D_{i,j,k}=D_{i,j,k-1}

因此,D_{i,j,k}=\mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})

在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。

算法描述[编辑]

Floyd-Warshall算法的描述如下:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

其中dist[i][j]表示由點i到點j的代價,當其為 ∞ 表示兩點之間沒有任何連接。

参考来源[编辑]

  1. ^ Stefan Hougardy. The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters. 2010-04, 110 (8-9): 279–281 [2015-04-11]. doi:10.1016/j.ipl.2010.02.001 (英文). 
  2. ^ Skiena, Steven. The Algorithm Design Manual 2. Springer. 2008-07-26: 212 [2015-04-11]. doi:10.1007/978-1-84800-070-4. ISBN 978-0073523408 (英文). 
  3. ^ Introduction to Algorithms [算法导论]. 机械工业出版社. 2006: 386 [2001]. ISBN 9787111187776 (中文(中国大陆)‎). 
  4. ^ Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh. Algorithms 1. McGraw-Hill Science/Engineering/Math. 2006-09-13: 176 [2015-04-11]. ISBN 978-0073523408 (英文). 

参见[编辑]