计算机科学

首页 > 计算机科学

Floyd-Warshall算法

2018-08-28 09:36:43     所属分类:图算法
Floyd-Warshall算法
分类 全局最短路径问题(适用于带权图)
数据结构
最坏时间复杂度
最优时间复杂度
最坏空间复杂度

Floyd-Warshall算法英语:Floyd-Warshall algorithm),中文亦称弗洛伊德算法,是解决任意两点间的最短路径的一种算法[1],可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包[2]

Floyd-Warshall算法的时间复杂度为[3],空间复杂度为

目录

  • 1 原理
  • 2 算法描述
  • 3 参考来源
  • 4 参见

原理

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

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

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

因此,

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

算法描述

Floyd-Warshall算法的描述如下:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    distvv ← 0
4 for each edge (u,v)
5    distuv ← 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 distij > distik + distkj 
10             distij ← distik + distkj
11         end if

其中distij表示由点到点的代价,当其为 ∞ 表示两点之间没有任何连接。

参考来源

  1. ^ Stefan Hougardy. The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters. 2010年4月, 110 (8-9): 279–281 [2015-04-11]. doi:10.1016/j.ipl.2010.02.001 (英语). 
  2. ^ Skiena, Steven. The Algorithm Design Manual (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) (英语). 
  3. ^ Introduction to Algorithms [算法导论]. 机械工业出版社. 2006: 386 2001. ISBN 9787111187776 (中文(大陆)‎). 
  4. ^ Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh. Algorithms (PDF) 1. McGraw-Hill Science/Engineering/Math. 2006-09-13: 176 [2015-04-11]. ISBN 978-0073523408. (原始内容 (PDF)存档于2015-02-13) (英语). 

参见

  • 图论最短路
  • Dijkstra算法
  • Bellman-Ford算法

上一篇:网络流
相关推荐