最短路问题

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：

  • 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用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


参见