查看“︁最短路问题”︁的源代码

{{Multiple issues|
{{unreferenced|time=2015-02-15T18:51:58+00:00}}
{{Expand language|1=en|time=2020-10-01T11:27:27+00:00}}
}}
{{NoteTA
|G1= IT
}}
[[File:6n-graf.svg|thumb|一个有6个节点和7条边的图]]
'''最短路径'''问题是[[图论]]研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
* '''确定起点的最短路径问题''' - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用[[Dijkstra算法]]，若边权为负时则适合使用[[Bellman-ford|Bellman-ford算法]]或者[[SPFA算法]]。
* '''确定终点的最短路径问题''' - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在[[无向图]]中该问题与确定起点的问题完全等同，在[[有向图]]中该问题等同于把所有路径方向反转的确定起点的问题。
* '''确定起点终点的最短路径问题''' - 即已知起点和终点，求两结点之间的最短路径。
* '''全局最短路径问题''' - 也叫多源最短路问题，求图中所有的最短路径。适合使用[[Floyd-Warshall算法]]。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
* [[Dijkstra算法]]
* [[A星算法|A*算法]]
* [[Bellman-Ford算法]]
* [[SPFA算法]]（Bellman-Ford算法的改进版本）
* [[Floyd-Warshall算法]]
* {{Tsl|en|Johnson's algorithm|Johnson最短路算法}}
* [[双向搜索]]

{{图算法}}

== 单源最短路径算法 ==

=== 无向图 ===
{| class="wikitable"
!权值要求
![[时间复杂度]]
!作者
|-
|ℝ<sub>+</sub>
|<math>O(V^2)</math>
|Dijkstra 1959
|-
|ℝ<sub>+</sub>
|<math>O((E + V) \log V)</math>
|Johnson 1977 ([[二叉堆]])
|-
|ℝ<sub>+</sub>
|<math>O(E + V \log V)</math>
|Fredman & Tarjan 1984 ([[斐波那契堆]])
|-
|ℕ
|<math>O(E)</math>
|Thorup 1999 (要求常数时间复杂度的乘法)。<br />
|}

=== 无权图 ===
{| class="wikitable"
!算法
!时间复杂度
!作者
|-
|[[广度优先搜索]]
|<math>O(E + V)</math>
|Konrad Zuse 1945,Moore 1959
|}

=== 有向无环图 ===
使用拓扑排序算法可以在有权值的DAG中以线性时间（<math>\theta(E+V)</math>）求解单源最短路径问题。

=== 无负权的有向图 ===
假设边缘权重均为整数。
{| class="wikitable"
!算法
!时间复杂度
!作者
|-
|
|''O''(''V'' <sup>2</sup>''EL'')
|Ford 1956
|-
|Bellman–Ford 算法
|''O''(''VE'')
|Shimbel 1955, Bellman 1958, Moore 1959
|-
|
|''O''(''V'' <sup>2</sup> log ''V'')
|Dantzig 1960
|-
|Dijkstra's 算法（列表）
|''O''(''V'' <sup>2</sup>)
|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'' log<sub>''E''/''V''</sub> ''L'')
|Gabow 1983, Gabow 1985
|-
|
|<math>O(E+V\sqrt {\log l})</math>
|Ahuja et al. 1990
|-
|Thorup
|''O''(''E'' + ''V'' log log ''V'')
|Thorup 2004<br />
|}

<br />{{算法}}

== 参见 ==
{{Portal|计算机科学|计算机程序设计}}
* [[图论]]
* [[离散数学]]
* [[算法导论]]
* [[寻路]]
* [[IEEE 802.1aq]]
* [[网络流]]
* [[最短路徑樹]]

{{Authority control}}
[[Category:图算法]]
[[Category:数据结构|Z]]
[[Category:多项式时间问题]]