Loading AI tools
来自维基百科,自由的百科全书
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:
用于解决最短路径问题的算法被称做“最短路径算法”,有时被简称作“路径算法”。最常用的路径算法有:
算法 | 时间复杂度 | 作者 |
---|---|---|
广度优先搜索 | 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 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.