最短路算法1——Dijkstra

概述

最短路径问题有众多的算法,对于无权图的最短路径 DFS与BFS 就可以轻松解决。而对于有权图来说就相对复杂一些,接下来要介绍的就是一种求有权图的单源最短路径的算法—— Dijkstra 算法。需要注意的是这里的 Dijkstra 算法要求图中不能出现负值圈负权边,出现负值圈在 Dijkstra 算法的某些优化下会造成程序的无限循环(可处理),而出现负权边会得出错误结果。

负权边的错例:Dijkstra 的局限

思想

无权图可以认为是特殊的有权图,只是它的边权全都为 $1$ 。想一想 BFS 是怎么找到最短路径的,它是通过一层一层的扩展,按照非递减的顺序去收录每个点。Dijkstra 算法的思想也是按照非递减的顺序收录每个点,最终找到最短路径。 与 BFS 不同的是,有权图中什么算一层呢?实际上 BFS 说是按层扩展,另一种理解可以是按照距离的从近到远去扩展。Dijkstra 算法就是每次收录一个距离最近且未被收录的点。这里还有一些小问题,比如收进来的点会不会影响其他点到起始点的距离?怎么初始化?怎么找出最近的点?我们先上代码之后给出答案。

实现

代码:
Ubuntu Pastebin : https://pastebin.ubuntu.com/p/vfwbH7QHF3/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int MAX_N = 100;

int map[MAX_N][MAX_N]; // 使用邻接矩阵表示图
bool collected[MAX_N]; // 每个结点是否被收录
int dist[MAX_N]; // 每个结点到起始点的距离
int path[MAX_N]; // 最短路径中的每个结点的上一个节点的下标
int n; // 结点个数

void init() // 初始化
{
memset(collected,false,sizeof(collected));
memset(dist,0x7f,sizeof(dist));
memset(path,-1,sizeof(path));
}

void Dijkstra(int start)
{
init();

dist[start] = 0;

while(true){
int min = INT_MAX;
int min_index = -1;
for( int i = 1; i <= n; i++){
if(min > dist[i] && !collected[i]){
min = dist[i];
min_index = i;
}
} //找出最近的未被收录的点
if(min_index == -1){ //如果找不到,跳出循环
break;
}

collected[min_index] = true; //将该点收录,
for( int i = 1; i <= n; i++){ //遍历该点的邻接点
if(map[min_index][i] != -1 && !collected[i]){
int temp = dist[min_index] + map[min_index][i];
if(temp < dist[i]){
dist[i] = temp;
path[i] = min_index;
}
}
}
}
}

核心步骤

  1. 初始化(包含更新起始点 dist 值)
  2. 找到并收录最近的未被收录的点
  3. 更新该点的邻接点
  4. 循环 $1,2$ 直至所有连通点均被收录

dist 数组中保存着什么?它保存的是从起点开始经过已被收录的点到达每个点的最短距离,初始状态下没有任何点被收录所以全为正无穷。 当程序将一个最近的点收录进来时,该点是有可能会影响其他的点到起始点的距离。

比如这个图,从 $1$ 走到 $3$。我们先收录了 $1$ 点,更新 $2$ 的距离为 $1$ ,$3$ 的距离为 $5$,下一步我们将收录 $2$ ,收录之后就会影响到它的邻接点(也就是 $3$ )的距离。我们会把 $3$ 的距离更新为 $2$ 。这就是 36-44 行的意义。

  • 初始化问题: 一开始将所有点的距离初始化为正无穷,将路径数组初始化为 $-1$。如果最终某点的距离仍为正无穷或路径数组仍为 $-1$,说明该点到起始点之间不连通。
  • 重边问题:如果图用邻接表来表示的话不会有重边问题,而邻接矩阵的话如果两点间有很多条边,它只会保存最后插入的边。如果是最短路问题的话我们可以在插入边时检查当前这条边的权重是否小于之前插入的边,是则插入覆盖,否则不插入当前边。
  • 输出路径问题:一般的可以用一个栈依次压入 path 数组中的值,再将它们依次弹出输出。有些题目给的是一个无向图且只问起点与终点的最短路径,这样的话我们可以颠倒起点和终点,path 数组也就被颠倒就不用栈就输出最短路径了。

优化

我们上面的代码最浪费时间的就是找出未收录的点中最近的点的操作,每次都要遍历所有的点去查找。我们可以用一个优先队列或最小堆去优化它。接下来我先给出利用优先队列优化后的代码,此代码将用邻接表来保存图以区别于之前的代码,帮助大家更好的了解 Dijkstra 算法的各种实现。

利用STL库中的优先队列优化

代码:
Ubuntu Pastebin : https://paste.ubuntu.com/p/ttngrNMyf7/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int MAX_N = 100;

struct edge { int next, weight;};
typedef pair<int ,int> P;

vector<edge>G[MAX_N]; //邻接表表示的图

int dist[MAX_N];
int path[MAX_N];

void Dijkstra(int start)
{
priority_queue<P, vector<P>, greater<P> >que;
//建立一个以小数值为高优先级的的优先队列
dist[start] = 0;

que.push(P(0,start)); //将起始点入队

while(!que.empty()){
//如果队列为空,说明所有点都已被收录,结束该算法
P p = que.top();
que.pop();
int v = p.second;
if(dist[v] < p.first){
//如果找到的节点不符合非递减规则,找下一个队列中的节点
continue;
}

for( int i = 0; i < G[v].size(); i++){
edge e = G[v][i];
if(dist[e.next] > dist[v] + e.weight){
dist[e.next] = dist[v] + e.weight;
path[e.next] = v;
que.push(P(dist[e.next],e.next));
//将邻接点入队
}
}
}
}

这里我们看到跟之前的代码逻辑可能有一些不太一样,按照之前的逻辑 while 循环应该按下面的方式实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while(!que.empty()){    
//如果队列为空,说明所有点都已被收录,结束该算法
P p = que.top();
que.pop();
int v = p.second;
collected[v] = true;

for( int i = 0; i < G[v].size(); i++){
edge e = G[v][i];
if(!collected[e.next]
&& dist[e.next] > dist[v] + e.weight)
{
dist[e.next] = dist[v] + e.weight;
path[e.next] = v;
if(!in_que[e.next]){
//在定义一个全局的bool数组标记点是否入队
que.push(P(dist[e.next],e.next));
//将邻接点入队
in_que[e.next] = true;
}
}
}
}

这是很常见的一种错误优化,我之前也写出过这样的代码。错误是因为已入队的元素是无法实时更新,无法保证更新 dist 数组时同时更新队列中的元素,所以我们改为允许结点多次入队不收录它,像之前的代码虽然效率有所下降但保证了代码的正确性。

利用最小堆优化

使用优先队列优化时遇到的问题是不能及时更新队列中元素的信息,而最小堆可以快速的查找删除再插入可以随时更新想更新的结点的信息,解决之前使用STL库中的优先队列所遇到的问题。
代码:
Ubuntu Pastebin : https://paste.ubuntu.com/p/thKfPjDRvd/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int MAX_N = 100;

struct edge { int next, weight;};
typedef pair<int ,int> P;

vector<edge>G[MAX_N]; //邻接表表示的图

int dist[MAX_N];
int path[MAX_N];
bool collected[MAX_N]; //标记每个顶点是否被收录

void Dijkstra(int start)
{
set<P, less<P> > min_heap;
//用 set 来伪实现一个小根堆,并具有映射二叉堆的功能。
dist[start] = 0;

min_heap.insert(make_pair(0, start));
collected[start] = true;
while(min_heap.size()){
//如果堆为空,说明所有点都已被收录,结束该算法
auto iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
collected[v] = true;
for( int i = 0; i < G[v].size(); i++){
edge e = G[v][i];
if(!collected[e.next]
&& dist[e.next] > dist[v] + e.weight)
{
min_heap.erase(make_pair(dist[e.next], e.next));
//删除之前插入堆中的数据
dist[e.next] = dist[v] + e.weight;
path[e.next] = v;
min_heap.insert(make_pair(dist[e.next], e.next));
//更新之后重修插入该结点
}
}
}
}

时间复杂度分析

$V$ 代表结点的个数,$E$ 代表边的个数。

  • 完全没有优化:每个顶点被收录一次,所以外层的 while 循环是 $O(V)$ 的,while中每次需要遍历一次所有的顶点,又是一个 $O(V)$ 的扫描。再加上每条边都要被访问一次时间复杂度为 $O(V^2 + E)$。
  • 利用优先队列优化:虽然节点会多次入队,但每条边最多导致一次入队,所以其时间复杂度为 $O( E \log E )$。
  • 利用最小堆优化:利用最小堆之后我们不用在内层需要进行 $O(V)$ 的扫描了,获得最近的结点的操作时间复杂度变为 $O(\log V)$,而每次更新 dist 数组的操作因为要删除再插入堆中复杂度从 $O(1)$ 变为 $O(\log V)$。总体的时间复杂度为 $O( (V + E) \log V )$。

对于一个稀疏图来说利用最小堆做优化后效率会高很多,而对于一个稠密图来说两者效率是差不多的。利用优先队列的优化方式编程复杂度相对最小堆优化的方式会低一些,方便快速实现该算法。

Demo & Keynote

我讲解 Dijkstra 算法用的课件中附有算法的动画演示,希望对大家理解 Dijkstra 算法有所帮助。
HTML版本在 GitHub Pages 托管,可 在线放映下载
如需 Keynote 版本请联系我 pazyx728@gmail.com
课件采用署名(BY)-非商业性(NC)-相同方式分享(SA)协议发布,请大家维护互联网底线。

参考资料

  • [1]邓俊辉.数据结构(C++语言版)[M].北京:清华大学出版社,2013.
  • [2]陈越.最短路径算法-讲义.[DB/OL].数据结构(浙江大学),2018.
  • [3]郭炜.程序设计与算法(二)算法基础[EB/OL].uml,2017-11-13/2018-11-30.

本文标题:最短路算法1——Dijkstra

文章作者:赵砚潇

发布时间:2018年03月23日 - 02:03

最后更新:2020年06月08日 - 22:06

原始链接:https://blog.zyx.sh/2018/03/23/dijkstra/

许可协议: 署名-非商业性使用-相同方式分享 4.0 国际 转载请保留原文链接及作者。

Donate comment here