Floyd-Warshall算法

算法英語:),中文亦称弗洛伊德算法佛洛依德算法[1],是解决任意两点间的最短路径的一种算法[2],可以正確處理有向圖或负权(但不可存在负权回路)的最短路径問題,同时也被用于计算有向图的传递闭包[3]

Floyd-Warshall算法
概况
類別全局最短路径问题(适用于带权图)
資料結構
复杂度
平均時間複雜度
最坏时间复杂度
最优时间复杂度
空間複雜度
相关变量的定义

算法的时间复杂度[4]空间复杂度

原理

算法的原理是动态规划[5]

为从的只以集合中的节点为中间節点的最短路径的长度。

  1. 若最短路径经过点k,则
  2. 若最短路径不经过点k,则

因此,

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

算法描述

算法的伪代码描述如下:

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]表示由點到點的代價,當其為 ∞ 表示兩點之間沒有任何連接。

使用动态规划的算法

实现

Floyd算法在不同的编程语言中均有大量的实现方法:

参考来源

  1. 杨军庆、安容瑾、任志国、张潇赟、蔡晓龙. . 《甘肃科技纵横》. 2010年, (5): 28-29 [2020-08-09]. (原始内容存档于2011-02-24).
  2. Stefan Hougardy. . Information Processing Letters. 2010年4月, 110 (8-9): 279–281 [2015-04-11]. doi:10.1016/j.ipl.2010.02.001. (原始内容存档于2015-09-24) (英语).
  3. Skiena, Steven. (PDF) 2. Springer. 2008-07-26: 212 [2015-04-11]. ISBN 978-0073523408. doi:10.1007/978-1-84800-070-4. (原始内容 (PDF)存档于2015-06-09) (英语).
  4. [算法导论]. 机械工业出版社. 2006: 386 [2001]. ISBN 9787111187776 (中文(中国大陆)‎).
  5. Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh. (PDF) 1. McGraw-Hill Science/Engineering/Math. 2006-09-13: 176 [2015-04-11]. ISBN 978-0073523408. (原始内容 (PDF)存档于2015-02-13) (英语).

参见

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.