【期末复习】例题讲解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到各个顶点的最短路径。