计算机科学

首页 > 计算机科学

戴克斯特拉算法

2018-08-28 09:36:14     所属分类:图算法
戴克斯特拉算法演示

戴克斯特拉算法英语:Dijkstra's algorithm,又译迪杰斯特拉算法)由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体;戴克斯特拉的原始版本找到两个顶点之间的最短路径,但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径,产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。

该算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 uv 有路径相连。我们以 E 表示G中所有边的集合,而边的权重则由权重函数 w: E → 0, ∞ 定义。因此,w(u, v) 就是从顶点 u 到顶点 v 的非负权重(weight)。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知 V 中有顶点 st,Dijkstra 算法可以找到 st 的最低权重路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。

最初的戴克斯特拉算法不采用最小优先级队列,时间复杂度是(其中为图的顶点个数)。通过斐波那契堆实现的戴克斯特拉算法时间复杂度是 (其中是边数) (Fredman & Tarjan 1984)。对于不含负权的有向图,这是目前已知的最快的单源最短路径算法。

目录

  • 1 算法描述
  • 2 时间复杂度
  • 3 相关问题及算法
  • 4 参考
  • 5 参考源程序
  • 6 外部链接

算法描述

上图为戴克斯特拉算法应用示意图。
起点以左下角的红点目标是右上角的绿点中间灰色的倒L型为障碍物蓝色空圈表示"暂定",用以搜索下一步;已经填充颜色的表示探访过,图中颜色以红到绿,越绿表示离起点越远。所有节点都被均匀的探索。

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时,原点 s 的路径权重被赋为 0 (ds = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dm设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于所有顶点的集合 V 中的任意顶点 v, 若 v 不为 s 和上述 m 之一, dv = ∞)。当算法结束时,dv 中存储的便是从 sv 的最短路径,或者如果路径不存在的话是无穷大。

边的拓展是Dijkstra 算法的基础操作:如果存在一条从 uv 的边,那么从 sv 的最短路径可以通过将边(u, v)添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 du + w(u, v)。如果这个值比目前已知的 dv 的值要小,我们可以用新值来替代当前 dv 中的值。拓展边的操作一直运行到所有的 dv 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 du 达到其最终值时,每条边(u, v)都只被拓展一次。

算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 dv 值的顶点 v ,而集合 Q 则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 du 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中,算法对 u 的每条外接边 (u, v) 进行拓展。

下面的伪代码计算并保留图G中原点s到每一顶点v的最短距离dv,同时找出并保留v在此最短路径上的“前趋”,即沿此路径由s前往v,到达v之前所到达的顶点。其中,函数Extract_Min(Q) 将顶点集合Q中有最小du值的顶点u从Q中删除并返回u。

 1  function Dijkstra(G, w, s)
 2     for each vertex v in VG        // 初始化
 3           dv := infinity           // 将各点的已知最短距离先设成无穷大
 4           previousv := undefined   // 各点的已知最短路径上的前趋都未知
 5     ds := 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 dv > du + w(u,v)             // 拓展边(u,v)。w(u,v)为从u到v的路径长度。
13                        dv := du + w(u,v)         // 更新路径长度到更小的那个和值。
14                        previousv := u              // 纪录前趋顶点

如果我们只对在 st 之间查找一条最短路径的话,我们可以在第9行添加条件如果满足 u = t 的话终止程序。

通过推导可知,为了记录最佳路径的轨迹,我们只需记录该路径上每个点的前趋,即可通过迭代来回溯出 st 的最短路径(当然,使用后继节点来存储亦可。但那需要修改代码):

1 s := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previousu      //previous数组即为上文中的p

现在序列 S 就是从 st 的最短路径的顶点集。

时间复杂度

我们可以用大O符号将该算法的运行时间表示为边数和顶点数的函数。

对于基于顶点集的实现,算法的运行时间是,其中分别表示完成键的降序排列时间和从中提取最小键值的时间。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合,所以搜索中最小元素的运算(Extract-Min())只需要线性搜索 中的所有元素。这样的话算法的运行时间是

对于边数少于的稀疏图来说,我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点(Extract-Min)。当用到二叉堆的时候,算法所需的时间为,斐波纳契堆能稍微提高一些性能,让算法运行时间达到。然而,使用斐波纳契堆进行编程,常常会由于算法常数过大而导致速度没有显著提高。

相关问题及算法

开放最短路径优先算法是该算法在网络路由中的一个具体实现。

与 Dijkstra 算法不同,Bellman-Ford算法可用于具有负花费边的图,只要图中不存在总花费为负值且从源点 s 可达的环路(如果有这样的环路,则最短路径不存在,因为沿环路循环多次即可无限制的降低总花费)。在可能有环路的情况下,Bellman-Ford算法则可以通过检测程序while循环次数是否大于|V|来进行判断。

与最短路径问题相关最有名的一个问题是旅行商问题,此类问题要求找出恰好通过所有目标点一次且最终回到原点的最短路径。然而该问题为NP-完全的;换言之,与最短路径问题不同,旅行商问题不太可能具有多项式时间解法。

如果有已知信息可用来估计某一点到目标点的距离,则可改用A*搜索算法,以减小最短路径的搜索范围。

参考

  • 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 		v=v; w=w; next=next;
14 	}
15 }emaxn;
16 int frontmaxn, tot=0;
17 
18 int Addedge(int u, int v, int w) {
19 	tot++;
20 	etot.v = v;
21 	etot.w = w;
22 	etot.next = frontu;
23 	frontu = tot;
24 }
25 
26 int N, M, S;
27 
28 void Readin() {
29 	ios::sync_with_stdio(false);
30 	cin >> N >> M >> S;
31 	for(int i = 1; i <= M; i++) {
32 		int u, v, w;
33 		cin >> u >> v >> w;
34 		Addedge(u, v, w);
35 	}
36 }
37 
38 struct Heap {
39 	int id, w;
40 	bool operator < (const Heap &rhs) const {
41 		return w < rhs.w;
42 	}
43 };
44 
45 int dismaxn;
46 int Dijkstra(int s) {
47 	priority_queue<Heap> q;
48 	for(int i = 1; i <= N; i++) disi = 2147483647;
49 	diss = 0;
50 	q.push(Heap{s, diss});
51 	while(!q.empty()) {
52 		Heap x = q.top(); q.pop();
53 		if(disx.id != x.w) continue;
54 		for(int i = frontx.id; i != 0; i = ei.next) {
55 			int k = ei.v;
56 			if(disk > disx.id + ei.w) {
57 				disk = disx.id + ei.w;
58 				q.push(Heap{k, disk});
59 			}
60 		}
61 	}
62 	for(int i =  1; i <= N; i++) cout << disi << ' ';
63 	cout << endl;
64 	return 0;
65 }

外部链接

  • 迪科斯彻算法分解演示视频(优酷)
  • Animation of Dijkstra's algorithm
  • The Boost Graph Library (BGL)
  • Interactive Implementation of Dijkstra's Algorithm
  • Shortest Path Problem: Dijkstra's Algorithm
  • 迪科斯彻算法的描述和证明(英文)[失效链接]

相关推荐