【期末复习】例题讲解Dijkstra算法

使用场景

Dijkstra算法用于解决单源点最短路径问题，即给一个顶点作为源点，依次求它到图中其他n-1个顶点的最短距离。

例题讲解

Dijkstra算法将图中所有顶点分成两部分，第一部分是已知到源点最短距离的顶点Known(K)，第二部分是不知道到源点最短距离的顶点Unknown(U)。初始化K中只有源点一个顶点，U中有n-1个顶点。如下图，我们求源点1到终点7的最短路径。

根据上图，可以得到如下表：

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	2	无穷
		3	无穷
		4	无穷
		5	无穷
		6	无穷
		7	无穷

1-1. 找到顶点1的邻接点2和3，然后更新它们到源点1的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	2	2
		3	5
		4	无穷
		5	无穷
		6	无穷
		7	无穷

1-2. 更新K,U中的顶点。发现U中2到源点的距离最小，把2加入K中得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	3	5
2	2	4	无穷
		5	无穷
		6	无穷
		7	无穷

2-1. 找到2的邻接点4和5，更新它们到源点的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	3	5
2	2	4	6+2=8
		5	8+2=10
		6	无穷
		7	无穷

2-2. 更新K,U中的顶点。发现U中3到源点距离最小，把3加入K中得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	4	8
2	2	5	10
3	5	6	无穷
		7	无穷

3-1. 找到3的邻接点4和6，更新它们到源点的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	4	5+1=6
2	2	5	10
3	5	6	6+5=11
		7	无穷

3-2. 更新K,U中的顶点。发现U中4到源点的距离最短，把4加入K中得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	5	10
2	2	6	11
3	5	7	无穷
4	6

4-1. 找到4的邻接点5和6，更新它们到源点的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	5	2+6=8
2	2	6	1+6=7
3	5	7	无穷
4	6

4-2. 更新K,U中的顶点。发现6到源点的距离最短，把6加入K中加入得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	5	8
2	2	7	无穷
3	5
4	6
6	7

5-1. 找到6的邻接点7，更新7到源点的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	5	8
2	2	7	7+6=13
3	5
4	6
6	7

5-2. 更新K,U中的顶点。K中5到源点的距离最小把5加入K中得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	7	13
2	2
3	5
4	6
6	7
5	8

6-1. 找到5的邻接点7,更新7到源点的距离得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0	7	3+8=11
2	2
3	5
4	6
6	7
5	8

6-2. 更新K,U中的顶点，将顶点7加入K中完成计算得到下表

K	K中顶点到源点的距离	U	U中顶点到源点的距离
1	0
2	2
3	5
4	6
6	7
5	8
7	11

由此我们就得到源点1到各个顶点的最短路径。