最短路問題

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

  • 確定起點的最短路徑問題 - 也叫單源最短路問題,即已知起始結點,求最短路徑的問題。在邊權非負時適合使用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


參見