【最短路径算法】#1 迪杰斯特拉Dijkstra_试实现迪杰斯特拉最短路径算法。 输入格式: 第1行输入结点数vexnum和边数arcnum。

Dijkstra算法

是计算机科学家迪杰斯特拉于1959年提出的算法。该算法可以解决非负权图上指定点到任一点的最短路径问题。时间复杂度在$O(n^2)$。

算法解析

此算法的核心思想是按照每个点到起点的最短距离（当前）依次遍历。每一步中距离最短的点的距离可被确定（可以设法证明），确定后再遍历这个点的邻接点并更新其最短距离。直到全图进入最终确定状态。其遍历元素为点（与其他算法可能有区别）。

我们以下图为例来说明Dijkstra算法的实现步骤。其中点v1为起点，每一步需要用到的点加粗强调。此后所有“路线”均指点到起点的最短路径。

建立一个数组用于存放起点到每个点的最短距离，并实时维护。其中起点到起点的距离为0，其余点的距离均为INF。
d i s = {   0 , − 1 , − 1 , − 1 , − 1 , − 1 , − 1   } dis=\set{0,-1,-1,-1,-1,-1,-1} dis={0,−1,−1,−1,−1,−1,−1}

此时在$dis$数组中选出未确定（初始时所有点均未确定）且离起点的最短距离最小的点，并以此点为目标，遍历更新其邻接点的路径距离。

显然目前距离最短的点为起点。因此下一步遍历起点的邻接点。

点v1的邻接点v7和v5均可以经过v1产生更短的路线，因此需要更新。更新后的路线为起点到目标点（v1）的距离+目标点到当前点的边线权值
d i s = {   0 , − 1 , − 1 , − 1 , 9 , − 1 , 1   } dis=\set{0,-1,-1,-1,9,-1,1} dis={0,−1,−1,−1,9,−1,1}
接下来根据“每步距离最短者确定最终线”，起点到“v1”的距离已经确定了。

我们在更新后的dis数组里再次找到其余点中距离最短的点。此点为v7。因此下一步遍历v7的邻接点。

同样滴，v7的邻接点v3和v6也都可以更新路径。长度为1（起点到v7的距离）+邻接边权值
d i s = {   0 , − 1 , 11 , − 1 , 9 , 7 , 1   } dis=\set{0,-1,11,-1,9,7,1} dis={0,−1,11,−1,9,7,1}
此时v7确定最短路径，其余的点中v6到起点的路径长度最小。接下来遍历v6的邻接点。

v6的邻接点有v4和v3，都可以更新，到v4的长度为7+1，到v3的长度为7+3。
d i s = {   0 , − 1 , 10 , 8 , 9 , 7 , 1   } dis=\set{0,-1,10,8,9,7,1} dis={0,−1,10,8,9,7,1}
确定v6最短路径，其余点中v4路径最短，但是点v4除v6外没有其他邻接点，因此可以直接纳入确定点集合。再从剩余点中选出路径最短的点。

此点为v5。接下来遍历其邻接点。

v5的邻接点只有v2一个，且可以更新路径。新路线长度为：9+3
d i s = {   0 , 12 , 10 , 8 , 9 , 7 , 1   } dis=\set{0,12,10,8,9,7,1} dis={0,12,10,8,9,7,1}
现在让我们看一下还有哪些点没确定
v = {   v 2 , v 3   } v=\set{v2,v3} v={v2,v3}
从这两个点中选出路径最短的点，自然是v3。但v3的所有邻接点（v7，v5，v6）都已经确定。再来看v2，v2的所有邻接点也都已经确定。

此时我们可以发现没有其他点还未确定最短路线，因此此图遍历完成。得到的最短路径数组如下：
d i s = {   0 , 12 , 10 , 8 , 9 , 7 , 1   } dis=\set{0,12,10,8,9,7,1} dis={0,12,10,8,9,7,1}

这就是Dijkstra算法。我个人觉得名字可怕，但真正理解后没啥难的。

模板题样例

下面我们用一道模板题来看一下Dijkstra算法的代码实现过程。

题目描述

罗老师在城市1，现在要到城市n参加聚会。路上会路过城市2~n-1。所有的城市间错综地连接了许多道路，每条道路的长度都不一样。现在罗老师想要知道从城市1到城市n最短距离是多少。

第一行输入两个数$n$和$m(1<=n<=2000,1<=m<=10000)$，接下来$m$行，每行输入三个整数$x,y,k$，表示城市$x,y$之间的道路长度为$k$。

输出一个整数，表示从$1$到$n$的最短路径。

数据样例

输入

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
1
2
3
4
5
6

输出

90
1

题目解析

如图，可以将城市和城市间的道路转化为一个无向图，要求即为求从1到5的最短路径，在此数据中为20+30+20+20=90。

对于这道题，我们可以直接用Dijkstra算法来解决。注意较大数据量时用链式前向星能减少空间浪费并适当增加遍历速度

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,minx;//定义输入用变量和算法中的辅助变量。
int d[100005],f[100005];//用于存储最短距离以及标记是否确定。
int head[100005],ne[100005],ver[100005],w[100005],tot;//链式前向星用数组
void add(int x,int y,int z){//链式前向星添加一条x到y的边z
	ne[++tot]=head[x],ver[tot]=y,w[tot]=z,head[x]=tot;
}
int main(){
	memset(d,0x3f,sizeof(d));//将距离设为无限
	memset(head,-1,sizeof(head));//将头指针指向-1
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c); add(b,a,c);//无向图要加两条边
	}
	d[1]=0;//起点到起点的距离为0
	for(int i=1;i<n;i++,minx=-1){//开始Dijkstra
		for(int j=1;j<=n;j++) if(!f[j]&&(minx==-1||d[minx]>d[j])) minx=j;
		//找到当前距离最短且未被确定过的点，存储其下标
		f[minx]=1;//标记表示已确定
		for(int j=head[minx];j!=-1;j=ne[minx]) d[ver[j]]=min(d[ver[j]],d[minx]+w[j]);
		//遍历此点所有临界点，更新维护最短路径
	}
	if(d[n]=0x3f3f3f3f) cout<<-1;//判断非连通图
	else cout<<d[n];
	return 0;
}
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

制作不易，点个赞罢