Dijkstra最短路算法_迪杰斯特拉最短路径的题目

导言

1. 本文立志做到通俗易懂，会有很多好看的图片(亲手画的~)来让各位理解，且不会涉及专业名词。
2. 为什么迪杰斯特拉算法可以算出最短路咧？有数学的方式可以证明，但我不会。所以在这里只演示步骤以及给出代码~
3. 本文将用一个例子来模拟迪杰斯特拉算法的过程，并会最后会以问答方式总结一下。

例子 (城市距离问题)

图中共有5个城市，编号从1到5，其中边中的红色数字是城市到城市的公路长度。
（例如：2号城市到4号城市的公路长度是50）

现在有个问题需要解决，我们想要求出1号城市到所有城市的最短距离。
图示如下：

为了区别起始地和目的地，下面我会在所有城市的后面小括号，表明它是起始地还是目的地，如：1号城市(起始地)
注意：在这里，1号城市比较特殊，因为1号城市即是起始地，又是目的地)。

---

这问题怎么解决呢？这就要用到迪杰斯特拉最短路算法啦~ 下面我用画图的方式来展示，迪杰斯特拉算法的步骤，之后我会总结步骤并给出代码。

首先，为了存储城市与城市的公路长度信息，我们可以定义一个二维数组 road (这个二维数组的专业名词叫邻接矩阵)。其中 road[3][4] 表示的就是3号城市和4号城市的公路长度。在这个图中，3号城市和4号城市的距离是 50 ，所以我们要把50赋予 road[3][4] ，由于路是双向的，所以 50 也要赋予 road[4][3] 。
最终，我们可以得到一个二维数组 road 。

这个二维数组中的 ∞ ，表示城市之间没有直接的公路相通，比如：road[5][2] == ∞，表示5号城市和2号城市没有直接的公路相通。
注意：这个二维数组图下面不会再看到…不太直观，只是给大家演示一下存储的结果。下面会有更直观的图)

---

接下来，为了存储1号城市(起始地)到所有城市(目的地)的最短距离，我们可以声明一个数组 dis ，默认值为无穷大。其中，dis[x] 表示1号城市(起始地)到x号城市(目的地)的距离，其中 x ∈ [1, 5]。(注意：这距离现在不是最短距离)，那现在dis数组如下：

那现在问题来了，我们怎么确定1号城市(起始地)到所有城市(目的地)的最短距离呢？我们可以再声明一个数组 mark ，默认值为 false 。其中，如果 mark[x] == true 的话，表示1号城市(起始地)到x号城市(目的地)的最短距离已经得到了，而且这个最短距离就存储在 dis[x] 中。

以上三个数组的声明如下：

// 声明
long long road[10][10];	// 存放公路长度 
bool mark[10];			// mark[x]表示：x号城市是否已是最短距离 
long long dis[10];		// dis[x]表示：1号城市(起始地)到x号城市(目的地)的距离 
1
2
3
4

在这里，我的空间开得大了一些。

---

因为此时我们是从1号城市(起始地)开始的，那我们可以得到什么呢？我们可以得到 1号城市(起始地)到1号城市(目的地)的距离就是 0，即dis[1] == 0。
注意：在这我们还无法确定1号城市(起始地)到1号城市(目的地)的最短距离就是 0，要等到 mark[1] == true 才能确定

---

那现在我们的所能得到的信息如下：
其中 ∞ 表示我们还不知道1号城市(起始地)到该城市(目的地)的距离。

下面，我们开始模拟迪杰斯特拉算法的过程啦。
先和大家说一下迪杰斯特拉的大概操作。

迪杰斯特拉算法需要循环 n 次，这个 n 是城市的个数。在这 n 次循环中，每次循环分为3步，通过这3步，我们可以得到其中一条，从1号城市(起始地)到其他城市(目的地)的最短路，即：每次循环我们可以得到一条最短路。
注意：其实最后一次循环我们可以不用，也就是我们也可以只循环 n - 1 次，下面会说明原因。

---

接下来，让我们进入迪杰斯特拉算法的世界！

循环第一次

第一步
遍历 dis 数组，求出 dis 数组中的最小值的索引(这个索引就是城市编号)。通过遍历，我们可以得到这个城市编号是 1 。这表示什么呢？这表示，此时，我们从1号城市(起始地)出发，到1号城市(目的地)的距离比到其他城市(目的地)的都小。那我们现在可以确定什么？我们现在就可以确定，1号城市(起始地)到1号城市(目的地)的最短距离已经找到了，距离为 0 。那既然我们找到了，我们现在就要进入迪杰斯特拉算法的第二步了。 (看不懂没关系，下面有步骤图)
简述：这一步的意思就是，通过dis数组，找到离1号城市(起始地)最近的城市(目的地)，那我们就可以得到，1号城市(起始地)到这个城市(目的地)的距离是最短距离。

第二步
标记我们找到的城市编号。我们第一步找到的城市编号是 1，那么这步就让 mark[1] = true ，这就表示我们找到了1号城市(起始地)到1号城市(目的地)的最短距离。 (看不懂没关系，下面有步骤图)
简述：这一步就是进行简单的标记。表示我们已经找到了其中一个城市(目的地)的最短路

第三步
接下来，我们以这个城市(目的地)为中间城市，进行更新 dis 数组。这是算法的第三步。
我们现在进入更新步骤。我们现在就是来判断，通过1号城市(目的地)，我们是否可以更近的到达其他城市(目的地)。
我先给大家画个图，其中左边的图表示1号城市(目的地)的公路信息，右边的图是通过1号城市(目的地)更新完毕后的 dis 数组，至于 dis 数组怎么变成这个样子，下面会有步骤解释哒。 (看不懂没关系，下面有步骤图)
先解释一下这里的图文。在这里，绿色背景的城市编号表示：该城市给标记了，这也说明了该城市的最短距离已经得到了，而最短距离就存储在 dis 数组中。而在 dis 数组中，橙色字体的数字，表示该城市的距离被更新了。(如2号、3号、5号城市)

---

我们先看到左边这个图，从第一二步，我们已经知道了1号城市(起始地)到1号城市(目的地)的最短距离了，那么现在我们如何更新呢？

我们知道，如果现在从1号城市(目的地)出发(即以1号城市(目的地)作为中间城市)，到x号城市(目的地)的距离是：dis[1] + road[1][x]，这条路线表示，再从1号城市(起始地)到x号城市的过程中，我们会经过1号城市(目的地)。
而对于x号城市(目的地)来说，dis 数组也存储了它当前的距离信息：dis[x]。
那么我们现在就要比较一下：dis[1] + road[1][x] 和 dis[x] 谁大谁小，并把小的值赋予 dis[x] 。
在这要解释一下，为什么要这样做。

这有三种情况：

1. 当 dis[1] + road[1][x] < dis[x]，这表示经过1号城市(目的地)，我们可以缩短从1号城市(起始地)到x号城市(目的地)的距离，此时把 dis[1] + road[1][x] 赋予 dis[x] 。
2. 当 dis[1] + road[1][x] > dis[x]，这表示经过1号城市(目的地)，我们不能缩短从1号城市(起始地)到x号城市(目的地)的距离，此时不赋予。
3. 当 dis[1] + road[1] == dis[x] 时，是否经过1号城市(目的地)，都对1号城市(起始地)到x号城市(目的地)的距离没影响，此时赋予不赋予都一样。 (看不懂没关系，下面有步骤图)

简述：简单来说，第三步的任务，就是通过我们一二步得到的这个中间城市，来更新 dis 数组。

---

我们再来看个图，看看我们究竟做了哪些步骤。

由于1号城市比较特殊(因为它既是起始地又是目的地)…上面有的地方可能难以理解…我们来看看下面，这次我们不再是特殊的1号城市了。

---

到目前为止，我们已经得到了1号城市(起始地)到1号城市(目的地)的最短距离了，我们现在只获得了1个，那接下来怎么做呢？

很简单，我们重复上面这三步就可以了!

---

循环第二次

第一步 (找出 dis 数组中的最小值的城市编号)
遍历 dis 数组后，我们发现 dis[5] 是最小的，所以 dis 数组中的最小值的城市编号就是 5，即5号城市。

第二步 (标记这个城市)
mark[5] = true ，表示我们已经得到了1号城市(起始地)到5号城市(目的地)的最短路径了。

第三步 (从这个城市出发，更新dis数组)
在这个步骤中，我们发现 dis[5] + road[5][4] < dis[4]的，所以我们把 dis[5] + road[5][4] 赋予 dis[4]，表示经过5号城市(目的地)，我们可以缩短1号城市(起始地)到4号城市(目的地)的距离。

这三步的过程图如下：
通过这三步后，我们可以得到1号城市(起始地)到1号城市(目的地)、和5号城市(目的地)的最短距离了。
现在的 dis 数组变成了：

其中绿色背景的表示已经是最短距离了，橙色字体的表示被更新了。

---

循环第三次

此时 dis 数组如下：

---

循环第四次

此时 dis 数组如下：

---

循环第五次

我们现在可以回答上面的问题了：

其实最后一次循环我们可以不用，也就是我们也可以只循环 n - 1 次，下面会说明原因。

你可以发现，这次循环完全可以不用执行，因为1号城市(起始地)到1号、3号、4号、5号城市(目的地)的最短距离已经得到了，我们不可能通过2号城市再更新：1号城市(起始地)到1号、3号、4号、5号城市(目的地)的最短距离了。

于是，我们最终的结果就是这样：

至此，我们就得到了1号城市到所有城市的最短距离，这个距离信息就存储在dis数组中。

---

迪杰斯特拉算法总过程

无论如何，因为我是按着自己的思路来的，大家可能听得云里雾里的，所以在下面，我会给出 dis 数组更新的全过程以及这个图，建议大家模拟一下迪杰斯特拉算法，理解下这个过程。

下面给出这个例题的迪杰斯特拉算法的完整代码 (建议看一次，里面有有用的注释~)

#include<bits/stdc++.h>
using namespace std;

long long road[10][10];	// 存放公路长度 
bool mark[10];		// x号城市是否已是最短距离 
long long dis[10];		// 1号城市(起始地)到x号城市(目的地)的距离 
long long n = 5;		// 本例中城市个数 
long long INF = 2E9;	// 假设∞为 2E9 


void Dijkstra(int beginCity){
	
	// 先初始化 
	for(int i=1;i<=n;i++){
		dis[i] = INF;
		mark[i] = false;
	}
	
	// 这句一定要记得写, 自己到自己的距离就是0 
	dis[beginCity] = 0; 
	
	// 这个外层的for只是起到了重复操作的作用
	for(int i=1;i<=n;i++){
		// 第一步(遍历) 
		long long minDis = INF;
		long long number = -1; 
		for(int t=1;t<=n;t++){
			if(mark[t] == true)continue;	// 这里要注意,已经是最短距离的要跳过,不
											// 然就会一直以这个城市为中间城市,去更新其他城市距离 
			if(minDis>dis[t]){
				minDis = dis[t];
				number = t;
			}
		}
		// 第二步(标记)
		mark[number] = true;
		
		// 第三步(更新)
		for(int x=1;x<=n;x++){
			if(mark[x] == true)continue;	 // 这句可要可不要,没有影响。 
			dis[x] = min(dis[x],dis[number] + road[number][x]);
		} 
	}
	// 看看结果对不对~ 
	for(int x=1;x<=n;x++){
		cout<<dis[x]<<" ";
	} 
	cout<<endl;
}

// 一个函数，方便录入公路信息 
void setRoad(long long a,long long b,long long length){
	road[a][b] = length;
	road[b][a] = length;
}

// 初始化城市关系图 
void init(){

	// 先认为所有城市都没有路,自己到自己的话公路长度为0 
	for(int i=1;i<=n;i++){
		for(int t=1;t<=n;t++){
			if(i == t) road[i][t] = 0;
			else road[i][t] = INF;
		}
	}
	
	// 输入公路信息
	setRoad(1,5,10);
	setRoad(1,2,50);
	setRoad(1,3,30);
	setRoad(2,3,5);
	setRoad(2,4,50);
	setRoad(3,4,50);
	setRoad(4,5,10);
}

int main(){	
	// 初始化城市关系图 
	init();
	
	// Dijkstra算法，我们现在要求的是从1号城市(起始地)到所有城市(目的地)的最短路 
	Dijkstra(1);	 
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

总结

问：迪杰斯特拉算法为了求出有 n 个点的图的最短路，需要循环多少次？
答：n - 1 次就够了。

问：迪杰斯特拉算法每次循环包括哪三步？
答：
1. 第一步，通过遍历，求出 dis 数组中最小值的索引。
2. 第二步，标记该索引的点，表示从起始点到该点已是最短路。
3. 第三步，更新 dis 数组，看看以该点为中间点，是否可以缩短距离。

拓展

推荐大家去AC了这道题，当做是一个练习，看看自己理解了没有(虽然我觉得有的地方我说得不好)，或者加深一下印象。

51nod_1953_物理地址查询

拓展题代码

#include<bits/stdc++.h>
using namespace std;

long long road[105][105];	// 存放传播时间 
bool mark[105];			// mark[x]表示：x计算机是否已经是最短传播时间 
long long dis[105];		// dis[x]表示：1号计算机(起始地)到x号计算机(目的地)的传输时间 
long long n;			// 本例中计算机个数 
long long INF = 2E9;	// 假设∞为 2E9 


// Dijkstra算法, beginComputer表示：起始传播的计算机 
void Dijkstra(int beginComputer){
	
	// 先初始化 
	for(int i=1;i<=n;i++){
		dis[i] = INF;
		mark[i] = false;
	}
	
	// 这句一定要记得写, 自己到自己的距离就是0 
	dis[beginComputer] = 0; 
	
	// 这个外层的for只是起到了重复操作的作用
	for(int i=1;i<=n-1;i++){
	
		// 第一步(遍历) 
		long long minDis = INF;
		long long number = -1; 
		for(int t=1;t<=n;t++){
			if(mark[t] == true)continue;	// 这里要注意,已经是最短距离的要跳过,不
											// 然就会一直以这个城市为中间城市,去更新其他城市距离 
			if(minDis>dis[t]){
				minDis = dis[t];
				number = t;
			}
		}
		
		// 第二步(标记)
		mark[number] = true;
		
		// 第三步(更新)
		for(int x=1;x<=n;x++){
			if(mark[x] == true)continue;	 // 这句可要可不要,没有影响。 
			dis[x] = min(dis[x],dis[number] + road[number][x]);
		} 
	}
}

// 一个函数，方便录入公路信息 
void setRoad(long long a,long long b,long long length){
	road[a][b] = length;
	road[b][a] = length;
}

// 一个函数，把字符串转为long long整数
long long strToLong(string s){
	long long a = 0;
	for(int i=0;i<s.length();i++){
		a = a * 10 + s[i] -'0';
	}
	return a;
} 


// 初始化计算机关系图 
void init(){
	
	// 输入计算机个数 
	cin>>n; 
	
	// 先认为所有计算机都不连通，只有自己和自己连通 
	for(int i=1;i<=n;i++){
		for(int t=1;t<=n;t++){
			if(i == t) road[i][t] = 0;
			else road[i][t] = INF;
		}
	}
	
	// 接受输入 
	string s;
	for(int i=2;i<=n;i++){
		for(int t=1;t<=i-1;t++){
			cin>>s;
			if(s == "x"){
				setRoad(i,t,INF);
			}else{
				setRoad(i,t,strToLong(s));
			}
		}
	}
}


int main(){	

	// 初始化计算机关系图 
	init();
	
	// Dijkstra算法，我们现在要求的是从1号计算机(起始地)到其他计算机(目的地)的最短传输时间，
	// 这些最短传输时间的最大值就是我们要的答案 
	Dijkstra(1);	
	
	// 我们现在已经求得了，从1号计算机(起始地)到其他计算机(目的地)的最短传输时间 (存储在dis数组中了) 
	// 这些最短传输时间的最大值就是我们要的答案
	long long m = 0;
	for(int i=1;i<=n;i++){
		m = max(dis[i],m);
	}
	cout<<m<<endl;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

最后

如果有讲错的地方，欢迎大家的指出。
如果觉得有所收获，请给我点个赞喔~ 拜拜~