最短路問題

最短路徑問題是圖論研究中的一個經典算法問題,旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。算法具體的形式包括:

  • 確定起點的最短路徑問題 - 也叫單源最短路問題,即已知起始結點,求最短路徑的問題。在邊權非負時適合使用Dijkstra算法,若邊權為負時則適合使用Bellman-ford算法或者SPFA算法
  • 確定終點的最短路徑問題 - 與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
  • 確定起點終點的最短路徑問題 - 即已知起點和終點,求兩結點之間的最短路徑。
  • 全局最短路徑問題 - 也叫多源最短路問題,求圖中所有的最短路徑。適合使用Floyd-Warshall算法
一個有6個節點和7條邊的圖

用於解決最短路徑問題的算法被稱做「最短路徑算法」,有時被簡稱作「路徑算法」。最常用的路徑算法有:

單源最短路徑算法

無向圖

權值要求 時間複雜度 作者
+   Dijkstra 1959
+   Johnson 1977 (二叉堆)
+   Fredman & Tarjan 1984 (斐波那契堆)
  Thorup 1999 (要求常數時間複雜度的乘法)。

無權圖

算法 時間複雜度 作者
廣度優先搜索   Konrad Zuse 1945,Moore 1959

有向無環圖

使用拓撲排序算法可以在有權值的DAG中以線性時間( )求解單源最短路徑問題。

無負權的有向圖

假設邊緣權重均為整數。

算法 時間複雜度 作者
O(V 2EL) Ford 1956
Bellman–Ford 算法 O(VE) Shimbel 1955, Bellman 1958, Moore 1959
O(V 2 log V) Dantzig 1960
Dijkstra's 算法(列表) O(V 2) Leyzorek et al. 1957, Dijkstra 1959, Minty (see Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstra's 算法(二叉堆) O((E + V) log V) Johnson 1977
…… …… ……
Dijkstra's 算法(斐波那契堆) O(E + V log V) Fredman & Tarjan 1984, Fredman & Tarjan 1987
O(E log log L) Johnson 1981, Karlsson & Poblete 1983
Gabow's 算法 O(E logE/V L) Gabow 1983, Gabow 1985
  Ahuja et al. 1990
Thorup O(E + V log log V) Thorup 2004


參見