最短路径Dijkstra算法详解

最短距离问题

最短路径问题

进阶--标尺增多

升级方法

例题应用

最短距离问题

Dijkstra算法的策略：

设置集合S存放已被访问的顶点，然后执行n次下面的两个步骤（n为顶点个数）：

（1）每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S（即令其已被攻占）。

（2）之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。

Dijkstra算法的具体实现：

由于Dijkstra算法的策略比较偏重理论化，因此为了方便编写代码，需要想办法来实现策略中两个较为关键的东西，即集合S的实现、起点s到达顶点 $V_{i}$ 的最短距离的实现。

（1）集合S可以用一个bool型数组vis[]来实现，即当vis[i]==true时表示顶点 $V_{i}$ 已被访问，当vis[i]==false时表示顶点 $V_{i}$ 未被访问。

（2）令int型数组d[]表示起点s到达顶点 $V_{i}$ 的最短距离，初始时除了起点s的d[s]赋为0，其余顶点都赋为一个很大的数，可以使用1000000.

邻接矩阵版

int n,G[maxn][maxn];
int d[maxn];
bool vis[maxn]={false};
void dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
				d[v]=d[u]+G[u][v];
			}
		}
	}
}

邻接表版

struct node{
	int v,dis;
};
vector<node> Adj[maxn];
int n;
int d[maxn];
bool vis[maxn]={false};
void dijkstra(){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int j=0;j<Adj[u].size();j++){
			int v=Adj[u][j].v;
			if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
				d[v]=d[u]+Adj[u][j].dis;
			}
		}
	}
}

上面的做法都是复杂度 $O\left ( V^{2} \right )$ 级别的，其中由于必须把每个顶点都标记为已被访问，因此外层循环的 $O\left ( V \right )$ 时间是无法避免的，但是寻找最小d[u]的过程却可以不必达到 $O\left ( V \right )$ 的复杂度，而可以使用堆优化来降低复杂度。最简洁的写法是直接使用STL中的优先队列，这样使用邻接表实现的Dijkstra算法的时间复杂度可以降为 $O\left ( VlogV+E \right )$ 。此外，Dijkstra算法只能应对所有边权都是非负数的情况，如果边权出现负数，那么Dijkstra算法很可能出错，这时最好用SPFA算法。

下面给出使用Dijkstra算法求解问题的完整算法模板：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000;
const int INF=1000000000;
int n,m,s,G[maxn][maxn];//顶点数，边数，起点 
int d[maxn];//起点到达各点的最短路径长度
bool vis[maxn]={false};
void dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
				d[v]=d[u]+G[u][v];
			}
		}
	}
}
int main(){
	int u,v,w;
	cin>>n>>m>>s;
	fill(G[0],G[0]+maxn*maxn,INF);//初始化图G
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		G[u][v]=w;
	} 
	dijkstra(s);
	for(int i=0;i<n;i++){
		cout<<d[i]<<" ";
	}
	return 0;
}

如果题目给出的是无向边而不是有向边，只需要把无向边当成两条指向相反的有向边即可。对邻接矩阵来说，一条u与v之间的无向边在输入时可以分别对G[u][v]和G[v][u]赋以相同的边权；而对邻接表来说，只需要在u的邻接表Adj[u]末尾添加上v，并在v的邻接表Adj[v]末尾添加上u即可。

最短路径问题

之前说的是在讲最短距离的求解，但是还没有讲到最短路径本身怎么求解。接下来叙述最短路径的求法。

只需要在求解最短距离的基础上，将路径信息记录下来，可以设置数组pre[]，令pre[v]表示从起点s到顶点v的最短路径上v的前一个顶点的编号。具体实现，以邻接矩阵作为举例：

int n,G[maxn][maxn];
int d[maxn];
int pre[maxn];
bool vis[maxn]={false};
void dijkstra(int s){
	fill(d,d+maxn,INF);
	for(int i=0;i<n;i++){
		pre[i]=i;
	}
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=IN&&d[u]+G[u][v]<d[v]){
				d[v]=d[u]+G[u][v];
				pre[v]=u;
			}
		}
	}
}

到这一步，求出了最短路径上每个点的前驱。当想知道整条路径时就可以用递归不断利用pre[]的信息寻找前驱，直至到达起点后从递归深处开始输出。

void dfs(int s,int v){//s为起点，v为当前访问的顶点 
	if(v==s){
		printf("%d\n",s);
		return;
	}
	dfs(s,pre[v]);
	printf("%d\n",v);
}

进阶--标尺增多

这种题目更多时候会出现有多条从起点到终点的最短路径，碰到这种有两条及以上可以达到最短距离的路径，题目就给出一个第二标尺，要求在所有最短路径中选择第二标尺最优的一条路径。而第二标尺常见的是以下三种出题方法或其组合：

（1）给每条边再增加一个权（比如说花费），然后要求在最短路径有多条时要求路径上的花费之和最小（如果边权有其他含义，也可以是最大）

（2）给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大（如果点权是其他含义的话也可以是最小）

（3）直接问有多少条最短路径。

对这三种出题方法，都只需要增加一个数组来存放新增的边权或点权或最短路径条数，然后在Dijkstra算法中修改优化d[v]的那个步骤即可，其他部分不需要改动。

下面对这三种出题方法对代码的修改给出解释：

（1）新增边权。以新增的边权代表花费为例，用cost[u][v]表示u->v的花费（由题目输入），并增加一个数组c[]，令从起点s到达顶点u的最小花费为c[u]，初始化时只有c[s]为0、其余c[u]均为INF。这样就可以在d[u]+G[u][v]<d[v]（即可以使s到v的最短距离d[v]更优）时更新d[v]和c[v]，而当d[u]+G[u][v]==d[v]（即最短距离相同）且c[u]+cost[u][v]<c[v]（即可以使s到v的最少花费更优）时更新c[v]，代码如下：

for(int v=0;v<n;v++){
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			c[v]=c[u]+cost[u][v];
		}
		else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
		     c[v]=c[u]+cost[u][v];
		}
	}
}

（2）新增点权。以新增的点权代表城市中能收集到的物资为例。用weight[u]表示城市u中的物资数目（由题目输入），并增加一个数组w[]，令从起点s到达顶点u可以收集到的最大物资为w[u]，初始化时只有w[s]为weight[s]，其余w[u]均为0。这样就可以在d[u]+G[u][v]<d[v]（既可以使s到v的最短距离d[v]更优）时更新d[v]和c[v]，而当d[u]+G[u][v]==d[v]（即最短距离相同）且w[u]+weight[v]>w[v]（即可以使s到v的最大物资数目更优）时更新w[v]。代码如下：

for(int v=0;v<n;v++){
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			w[v]=w[u]+weight[v];
		}
		else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
			w[v]=w[u]+weight[v];
		}
	}
}

（3）求最短路径条数。只需要增加一个数组num[]，令从起点s到达顶点u的最短路径条数为num[u]，初始化时只有num[s]=1、其余num[u]均为0.这样就可以在d[u]+G[u][v]<d[v]（即可以使s到v的最短距离d[v]更优）时更新d[v]，并让num[v]继承num[u]，而当d[u]+G[u][v]==d[v]（即最短距离相同）时将num[u]加到num[v]上。代码如下：

for(int v=0;v<n;v++){
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			num[v]=num[u];
		}
		else if(d[u]+G[u][v]==d[v]){
			num[v]+=num[u];
		}
	}
}

例题

给出N个城市，M条无向边，每个城市中都有一定数目的救援小组，所有边的边权已知。现在给出起点和终点，求从起点到终点的最短路径条数即最短路径上的救援小组数目之和。如果有多条最短路径，则输出数目之和最大的。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510;
const int INF=1000000000;
int n,m,st,ed,G[maxn][maxn],weight[maxn];//顶点数，边数，起点，终点
int d[maxn],w[maxn],num[maxn];
bool vis[maxn]={false};
void dijkstra(int s){
	fill(d,d+maxn,INF);
	memset(num,0,sizeof(num));
	memset(w,0,sizeof(w));
	d[s]=0;
	w[s]=weight[s];
	num[s]=1;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF){
				if(d[u]+G[u][v]<d[v]){
					d[v]=d[u]+G[u][v];
					w[v]=w[u]+weight[v];
					num[v]=num[u];
				}
				else if(d[u]+G[u][v]==d[v]){
					if(w[u]+weight[v]>w[v]){
						w[v]=w[u]+weight[v];
					}
					num[v]+=num[u];
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>st>>ed;
	for(int i=0;i<n;i++){
		cin>>weight[i];
	}
	int u,v;
	fill(G[0],G[0]+maxn*maxn,INF);
	for(int i=0;i<m;i++){
		cin>>u>>v;
		cin>>G[u][v];
		G[v][u]=G[u][v];
	}
	dijkstra(st);
	cout<<num[ed]<<" "<<w[ed]<<endl;
	return 0;
}

升级方法

上面给的三种情况都是以路径上边权或点权之和为第二标尺的。事实上也可能出现一些逻辑更为复杂的计算边权或点权的方式，此时按照上面的方式只使用dijkstra算法就不一定能算出正的结果（原因是不一定满足最优子结构），或者即便能算出，其逻辑也极其复杂。这里介绍一种更通用、又模板化的解决此类问题的方式--dijkstra+dfs。

只使用dijkstra算法时，算法中数组pre[]总是保持着最优路径，而这显然需要在执行dijkstra算法的过程中使用严谨的思路来确定何时更新每个结点v的前驱结点pre[v]，容易出错。事实上还有更简单的方法是：先在dijkstra算法中记录下所有最短路径（只考虑距离），然后从这些最短路径中选出一条第二标尺最优的路径（因为在给定一条路径的情况下，针对这条路径的信息都可以通过边权和点权很容易计算出来！）

（1）使用dijkstra算法记录所有最短路径

由于此时要记录所有最短路径，因此每个结点就会存在多个前驱结点，这样原先pre数组只能记录一个前驱结点的方法将不再适用。为了适应多个前驱的情况，不妨把pre数组定义为vector类型”vector<int> pre[maxn]"，这样对每个结点v来说，pre[v]就是一个变长数组vector，里面用来存放结点v的所有能产生最短路径的前驱结点。（对需要查询某个顶点u是否在顶点v的前驱中的题目，也可以把pre数组设置为set<int>数组，此时使用pre[v].count(u)来查询会比较方便）：

在此处的dijkstra算法部分，只需要考虑距离这一因素，因此不必考虑第二标尺的干扰，而专心于pre数组的求解。在之前的写法中，pre[i]被初始化为i，表示每个结点在初始状态下的前驱为自身，但是在此处，pre数组一开始不需要赋初值。

接下来就是考虑更新d[v]的过程中pre数组的变化。首先，如果d[u]+G[u][v]<d[v]，说明以u为中介点可以使d[v]更优，此时需要令v的前驱结点为u。并且即便原先pre[v]中已经存放了若干结点，此处也应当先清空，然后再添加u，如下面的代码所示。显然，对顶点v来说，由于每次找到更优的前驱时都会清空pre[v]，因此pre数组不需要初始化。

if(d[u]+G[u][v]<d[v]){
	d[v]=d[u]+G[u][v];
	pre[v].clear();
	pre[v].push_back(u);
}

之后，如果d[u]+G[u][v]==d[v]，说明以u为中介点可以找到一条相同距离的路径，因此v的前驱结点需要在原先的基础上添加上u结点（而不必先清空pre[v]），代码如下：

if(d[i]+G[u][v]==d[v]){
	pre[v].push_back(u);
}

这样就完成了pre数组的求解，完整的dijkstra算法部分代码如下所示，且对这一系列最短路的题目来说，下面的代码可以完全不修改而直接全部默写上去：

vector<int> pre[maxn];
void dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=INF;
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF){
				if(d[u]+G[u][v]<d[v]){
					d[v]=d[u]+G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				}
				else if(d[u]+G[u][v]==d[v]){
					pre[v].push_back(u);
				}
			}
		}
	}
}

（2）遍历所有最短路径，找到一条使第二标尺最优的路径

在之前的写法中曾使用一个递归来找出最短路径。此处的做法与之类似，不同点在于，由于每个结点的前驱结点可能有很多个，遍历的过程就会形成一棵递归树。

当对这棵树进行遍历时，每次到达叶子结点，就会产生一条完整的最短路径。因此，每得到一条完整路径，就可以对这条路径计算其第二标尺的值（例如把路径上的边权或是点权累加出来），令其与当前第二标尺的最优值进行比较。如果比当前最优值更优，则更新最优值，并用这条路径覆盖当前的最优路径。这样，当所有最短路径都遍历完毕后，就可以得到最有第二标尺与最优路径，

接下来就要考虑如何写DFS的递归函数。

首先，根据上面的分析，必须要有的是：

1.作为全局变量的第二标尺最优值optValue

2.记录最优路径的数组path（使用vector来存储）

3.临时记录dfs遍历到叶子结点时的路径tempPath（也使用vector存储）

由此就可以写出DFS的代码，如下所示：

int optValue;
vector<int> pre[maxn];
vector<int> path,tempPath;
void dfs(int v){
	if(v==st){
		tempPath.push_back(v);
		int value;
		if(value优于optvalue){
			optvalue=value;
			path=tempPath;
		}
		tempPath.pop_back();
		return;
	}
	tempPath.push_back(v);
	for(int i=0;i<pre[v].size();i++){
		dfs(pre[v][i]);
	}
	tempPath.pop_back();
}

上面的代码中只有一处是需要根据实际题目情况进行填充的（语句"value优于optvalue"只需要根据实际情况填写大写或者小写），即计算路径tempPath上的value值时。而这个地方一般会涉及路径边权或者点权的计算。需要注意的是，由于递归的原因，存放在tempPath中的路径结点是逆序的，因此访问结点需要倒着进行。当然，如果仅是对边权或点权进行求和，那么正序访问也是可以的。以计算路径tempPath上边权之和与点权之和的代码为例：

//边权之和 
int value=0;
for(int i=tempPath.size()-1;i>0;i--){
	int id=tempPath[i],idNext=tempPath[i-1];
	value+=V[id][idNext];
}
//点权之和 
int value=0;
for(int i=tempPath.size()-1;i>=0;i--){
	int id=tempPath[i];
	value+=w[id]; 
}

最后指出，如果需要同时计算最短路径的条数，那么既可以按之前的做法在dijkstra代码添加num数组来求解，也可以开一个全局变量来记录最短路径条数，当dfs到达叶子结点时令该全局变量加1即可。

例题应用

有N个城市（编号为0~N-1）、M条道路（无向边），并给出M条道路的距离属性与花费属性。现在给出起点S与终点D，求从起点到终点的最短路径、最短距离及花费。注意：如果有多条最短路径，则选择花费最小的那条。

思路

本题除了求最短距离外，还要求两个额外信息：最短路径以及最短路径上的最小花费之和，因此只使用dijkstra算法或是使用dijkstra+dfs都是可以的。另外，本题很适合作为这两种方法的练习。

（1）对只使用dijkstra算法的写法，令cost[maxn][maxn]表示顶点间的花费（也即边权），c[maxn]存放从起点s到达每个结点u的在最短路径下的最小花费，其中c[s]在初始化时为0。而针对最短路径，可以用int型pre数组存放每个结点的前驱，接下来就是按前面说的过程在最短距离的更新过程中同时更新数组c和数组pre。代码如下：

if(vis[v]==false&&G[u][v]!=INF){
	if(d[u]+G[u][v]<d[v]){
		d[v]=d[u]+G[u][v];
		c[v]=c[u]+cost[u][v];
		pre[v]=u;
	}
	else if(d[u]+G[u][v]==d[u]){
		if(c[u]+cost[u][v]<c[v]){
			c[v]==c[u]+cost[u][v];
			pre[v]=u;
		}
	}
}

（2）对使用dijkstra+dfs的写法，dijkstra的部分可以直接把之前给出的模板写上。至于dfs的部分，对当前得到的一条路径tempPath，需要计算出该路径上的边权之和，然后令其与最小边权minCost进行比较，如果新路径的边权之和更小，则更新minCost和最优路径path，核心路径如下

if(v==st){
	tempPath.push_back(v);
	int tempCost=0;
	for(int i=tempPath.size()-1;i>0;i--){
		int id=tempPath[i],idNext=tempPath[i-1];
		tempCost+=cost[id][idNext];
	}
	if(tempCost<minCost){
		minCost=tempCost;
		path=tempPath;
	}
	tempPath.pop_back();
	return;
}

完整代码

（1）dijkstra算法

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510;
const int INF=1000000000;
int n,m,st,ed,G[maxn][maxn],cost[maxn][maxn];
int d[maxn],c[maxn],pre[maxn];
bool vis[maxn]={false};
void dijkstra(int s){
	fill(d,d+maxn,INF);
	fill(c,c+maxn,INF);
	for(int i=0;i<n;i++){
		pre[i]=i;
	}
	d[s]=0;
	c[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF){
				if(d[u]+G[u][v]<d[v]){
					d[v]=d[u]+G[u][v];
					c[v]=c[u]+cost[u][v];
					pre[v]=u;
				}
				else if(d[u]+G[u][v]==d[v]){
					if(c[u]+cost[u][v]<c[v]){
						c[v]=c[u]+cost[u][v];
						pre[v]=u;
					}
				}
			}
		}
	}
}
void dfs(int v){
	if(v==st){
		cout<<v<<" ";
		return;
	}
	dfs(pre[v]);
	cout<<v<<" ";
}
int main(){
	cin>>n>>m>>st>>ed;
	int u,v;
	fill(G[0],G[0]+maxn*maxn,INF);
	for(int i=0;i<m;i++){
		cin>>u>>v;
		cin>>G[u][v]>>cost[u][v];
		G[v][u]=G[u][v];
		cost[v][u]=cost[u][v];
	}
	dijkstra(st);
	dfs(ed);//打印路径 
	cout<<d[ed]<<" "<<c[ed]<<endl;
	return 0;
}

（2）dijkstra+dfs

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=510;
const int INF=1000000000;
int n,m,st,ed,G[maxn][maxn],cost[maxn][maxn];
int d[maxn],minCost=INF;
bool vis[maxn]={false};
vector<int> pre[maxn];
vector<int> tempPath,path;
void dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1){
			return;
		}
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF){
				if(d[u]+G[u][v]<d[v]){
					d[v]=d[u]+G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				}
				else if(d[u]+G[u][v]==d[v]){
					pre[v].push_back(u);
				}
			}
		}
	}
}
void dfs(int v){
	if(v==st){
		tempPath.push_back(v);
		int tempCost=0;
		for(int i=tempPath.size()-1;i>0;i--){
			int id=tempPath[i],idNext=tempPath[i-1];
			tempCost+=cost[id][idNext];
		}
		if(tempCost<minCost){
			minCost=tempCost;
			path=tempPath;
		}
		tempPath.pop_back();
		return;
	}
	tempPath.push_back(v);
	for(int i=0;i<pre[v].size();i++){
		dfs(pre[v][i]);
	}
	tempPath.pop_back();
}
int main(){
	cin>>n>>m>>st>>ed;
	int u,v;
	fill(G[0],G[0]+maxn*maxn,INF);
	fill(cost[0],cost[0]+maxn*maxn,INF);
	for(int i=0;i<m;i++){
		cin>>u>>v;
		cin>>G[u][v]>>cost[u][v];
		G[v][u]=G[u][v];
		cost[v][u]=cost[u][v];
	}
	dijkstra(st);
	dfs(ed);
	for(int i=path.size()-1;i>=0;i--){
		cout<<path[i]<<" ";
	}
	cout<<d[ed]<<" "<<minCost<<endl;
	return 0;
}