Mixing
戴克斯特拉算法
戴克斯特拉算法演示
图与树 搜索算法 |
|---|
|
分类 |
|
相关主题 |
|
戴克斯特拉算法（英语：Dijkstra's algorithm，又译迪杰斯特拉算法）由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了廣度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体；戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该演算法可以用来找到两个城市之间的最短路径。
该演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負权重（weight）。邊的权重可以想像成兩個頂點之間的距離。任兩點間路徑的权重，就是該路徑上所有邊的权重總和。已知 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t 的最低权重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。
最初的戴克斯特拉算法不采用最小优先级队列，时间复杂度是O(|V|2){displaystyle O(|V|^{2})}
目录
1 算法描述
2 時間複雜度
3 相關問題及演算法
4 參考
5 参考源程序
6 外部連結
算法描述
上圖為戴克斯特拉演算法應用示意圖。
起點以左下角的紅點，目標是右上角的綠點，中間灰色的倒L型為障礙物。藍色空圈表示"暫定"，用以搜索下一步；已經填充顏色的表示探訪過，圖中顏色以紅到綠，越綠表示離起點越遠。所有節點都被均勻的探索。
這個算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時，原點 s 的路径权重被賦為 0 （d[s] = 0）。若对于顶点 m 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同時把所有其他（s不能直接到达的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（对于所有顶点的集合 V 中的任意頂點 v， 若 v 不为 s 和上述 m 之一， d[v] = ∞）。當算法結束時，d[v] 中儲存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無窮大。
邊的拓展是Dijkstra 算法的基礎操作：如果存在一條從 u 到 v 的邊，那麼從 s 到 v 的最短路徑可以通過將邊（u, v）添加到從 s 到 u 的路徑尾部來拓展一條從 s 到 v 的路徑。這條路徑的長度是 d[u] + w(u, v)。如果這個值比目前已知的 d[v] 的值要小，我們可以用新值來替代當前 d[v] 中的值。拓展邊的操作一直執行到所有的 d[v] 都代表從 s 到 v 的最短路徑的长度值。此算法的组织令 d[u] 達到其最終值时，每條邊（u, v）都只被拓展一次。
算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，算法對 u 的每条外接邊 (u, v) 進行拓展。
下面的伪代码计算并保留图G中原点s到每一顶点v的最短距离d[v]，同时找出并保留v在此最短路径上的“前趋”，即沿此路径由s前往v，到达v之前所到达的顶点。其中，函数Extract_Min(Q) 将頂點集合Q中有最小d[u]值的頂點u从Q中删除并返回u。
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 初始化
3 d[v] := infinity // 將各點的已知最短距離先設成無窮大
4 previous[v] := undefined // 各点的已知最短路径上的前趋都未知
5 d[s] := 0 // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijkstra演算法主體
9 u := Extract_Min(Q)
10 S.append(u)
11 for each edge outgoing from u as (u,v)
12 if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
13 d[v] := d[u] + w(u,v) // 更新路径长度到更小的那个和值。
14 previous[v] := u // 紀錄前趨頂點
如果我們只對在 s 和 t 之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足 u = t 的話終止程序。
通过推导可知，为了记录最佳路径的轨迹，我们只需记录该路径上每个点的前趋，即可通过迭代來回溯出 s 到 t 的最短路徑（当然，使用后继节点来存储亦可。但那需要修改代码）：
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u] //previous数组即为上文中的p
現在序列 S 就是從 s 到 t 的最短路徑的頂點集。
時間複雜度
我們可以用大O符號將该算法的運行時間表示為邊數m{displaystyle m}
对于基于顶点集Q{displaystyle Q}
Dijkstra算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q{displaystyle Q}
對於邊數少於n2{displaystyle n^{2}}
相關問題及演算法
開放最短路徑優先算法是该算法在網絡路由中的一個具體實現。
與 Dijkstra 算法不同，Bellman-Ford算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。在可能有环路的情况下，Bellman-Ford算法则可以通过检测程序while循环次数是否大于|V|来进行判断。
與最短路徑問題相關最有名的一個問題是旅行商問題，此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間解法。
如果有已知信息可用來估計某一點到目標點的距離，則可改用A*搜尋算法，以減小最短路徑的搜索範圍。
參考
.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms Second. MIT Press and McGraw–Hill. 2001: 595–601. ISBN 0-262-03293-7.
Dial, Robert B. Algorithm 360: Shortest-path forest with topological ordering [H]. Communications of the ACM. 1969, 12 (11): 632–633. doi:10.1145/363269.363610.
Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. 1984. doi:10.1109/SFCS.1984.715934.
Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the Association for Computing Machinery. 1987, 34 (3): 596–615. doi:10.1145/28869.28874.
Zhan, F. Benjamin; Noon, Charles E. Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transportation Science. February 1998, 32 (1): 65–73. doi:10.1287/trsc.32.1.65.
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. 1957.
Knuth, D.E. A Generalization of Dijkstra's Algorithm. Information Processing Letters. 1977, 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. Faster Algorithms for the Shortest Path Problem. Journal of Association for Computing Machinery (ACM). April 1990, 37 (2): 213–223. doi:10.1145/77600.77615.
Raman, Rajeev. Recent results on the single-source shortest paths problem. SIGACT News. 1997, 28 (2): 81–87. doi:10.1145/261342.261352.
Thorup, Mikkel. On RAM priority Queues. SIAM Journal on Computing. 2000, 30 (1): 86–109. doi:10.1137/S0097539795288246.
Thorup, Mikkel. Undirected single-source shortest paths with positive integer weights in linear time. journal of the ACM. 1999, 46 (3): 362–394 [2017-11-01]. doi:10.1145/316542.316548. （原始内容存档于2017-09-21）.
参考源程序
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cmath>
5 #include <queue>
6 using namespace std;
7
8 const int maxn = 500000 + 100;
9
10 struct edge {
11 int v, w, next;
12 edge(int v=0, int w=0, int next=0) : v(v), w(w), next(next) {
13 }
14 }e[maxn];
15 int front[maxn], tot=0;
16
17 int Addedge(int u, int v, int w) {
18 tot++;
19 e[tot].v = v;
20 e[tot].w = w;
21 e[tot].next = front[u];
22 front[u] = tot;
23 }
24
25 int N, M, S;
26
27 void Readin() {
28 ios::sync_with_stdio(false);
29 cin >> N >> M >> S;
30 for(int i = 1; i <= M; i++) {
31 int u, v, w;
32 cin >> u >> v >> w;
33 Addedge(u, v, w);
34 }
35 }
36
37 struct Heap {
38 int id, w;
39 bool operator < (const Heap &rhs) const {
40 return w < rhs.w;
41 }
42 };
43
44 int dis[maxn];
45 int Dijkstra(int s) {
46 priority_queue<Heap> q;
47 for(int i = 1; i <= N; i++) dis[i] = 2147483647;
48 dis[s] = 0;
49 q.push(Heap{s, dis[s]});
50 while(!q.empty()) {
51 Heap x = q.top(); q.pop();
52 if(dis[x.id] != x.w) continue;
53 for(int i = front[x.id]; i != 0; i = e[i].next) {
54 int k = e[i].v;
55 if(dis[k] > dis[x.id] + e[i].w) {
56 dis[k] = dis[x.id] + e[i].w;
57 q.push(Heap{k, dis[k]});
58 }
59 }
60 }
61 for(int i = 1; i <= N; i++) cout << dis[i] << ' ';
62 cout << endl;
63 return 0;
64 }
外部連結
- 迪科斯彻算法分解演示视频（优酷）
- Animation of Dijkstra's algorithm
- The Boost Graph Library (BGL)
- Interactive Implementation of Dijkstra's Algorithm
- Shortest Path Problem: Dijkstra's Algorithm
迪科斯彻算法的描述和证明（英文）[永久失效連結]
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments
Post a Comment