• 最短路径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.

    邻接矩阵版

    1. int n,G[maxn][maxn];
    2. int d[maxn];
    3. bool vis[maxn]={false};
    4. void dijkstra(int s){
    5. 	fill(d,d+maxn,INF);
    6. 	d[s]=0;
    7. 	for(int i=0;i<n;i++){
    8. 		int u=-1,MIN=INF;
    9. 		for(int j=0;j<n;j++){
    10. 			if(vis[j]==false&&d[j]<MIN){
    11. 				u=j;
    12. 				MIN=d[j];
    13. 			}
    14. 		}
    15. 		if(u==-1){
    16. 			return;
    17. 		}
    18. 		vis[u]=true;
    19. 		for(int v=0;v<n;v++){
    20. 			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
    21. 				d[v]=d[u]+G[u][v];
    22. 			}
    23. 		}
    24. 	}
    25. }

    邻接表版

    1. struct node{
    2. 	int v,dis;
    3. };
    4. vector<node> Adj[maxn];
    5. int n;
    6. int d[maxn];
    7. bool vis[maxn]={false};
    8. void dijkstra(){
    9. 	fill(d,d+maxn,INF);
    10. 	d[s]=0;
    11. 	for(int i=0;i<n;i++){
    12. 		int u=-1,MIN=INF;
    13. 		for(int j=0;j<n;j++){
    14. 			if(vis[j]==false&&d[j]<MIN){
    15. 				u=j;
    16. 				MIN=d[j];
    17. 			}
    18. 		}
    19. 		if(u==-1){
    20. 			return;
    21. 		}
    22. 		vis[u]=true;
    23. 		for(int j=0;j<Adj[u].size();j++){
    24. 			int v=Adj[u][j].v;
    25. 			if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
    26. 				d[v]=d[u]+Adj[u][j].dis;
    27. 			}
    28. 		}
    29. 	}
    30. }

    上面的做法都是复杂度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算法求解问题的完整算法模板：

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. using namespace std;
    5. const int maxn=1000;
    6. const int INF=1000000000;
    7. int n,m,s,G[maxn][maxn];//顶点数，边数，起点 
    8. int d[maxn];//起点到达各点的最短路径长度
    9. bool vis[maxn]={false};
    10. void dijkstra(int s){
    11. 	fill(d,d+maxn,INF);
    12. 	d[s]=0;
    13. 	for(int i=0;i<n;i++){
    14. 		int u=-1,MIN=INF;
    15. 		for(int j=0;j<n;j++){
    16. 			if(vis[j]==false&&d[j]<MIN){
    17. 				u=j;
    18. 				MIN=d[j];
    19. 			}
    20. 		}
    21. 		if(u==-1){
    22. 			return;
    23. 		}
    24. 		vis[u]=true;
    25. 		for(int v=0;v<n;v++){
    26. 			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
    27. 				d[v]=d[u]+G[u][v];
    28. 			}
    29. 		}
    30. 	}
    31. }
    32. int main(){
    33. 	int u,v,w;
    34. 	cin>>n>>m>>s;
    35. 	fill(G[0],G[0]+maxn*maxn,INF);//初始化图G
    36. 	for(int i=0;i<m;i++){
    37. 		cin>>u>>v>>w;
    38. 		G[u][v]=w;
    39. 	} 
    40. 	dijkstra(s);
    41. 	for(int i=0;i<n;i++){
    42. 		cout<<d[i]<<" ";
    43. 	}
    44. 	return 0;
    45. }

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

    最短路径问题

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

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

    1. int n,G[maxn][maxn];
    2. int d[maxn];
    3. int pre[maxn];
    4. bool vis[maxn]={false};
    5. void dijkstra(int s){
    6. 	fill(d,d+maxn,INF);
    7. 	for(int i=0;i<n;i++){
    8. 		pre[i]=i;
    9. 	}
    10. 	d[s]=0;
    11. 	for(int i=0;i<n;i++){
    12. 		int u=-1,MIN=INF;
    13. 		for(int j=0;j<n;j++){
    14. 			if(vis[j]==false&&d[j]<MIN){
    15. 				u=j;
    16. 				MIN=d[j];
    17. 			}
    18. 		}
    19. 		if(u==-1){
    20. 			return;
    21. 		}
    22. 		vis[u]=true;
    23. 		for(int v=0;v<n;v++){
    24. 			if(vis[v]==false&&G[u][v]!=IN&&d[u]+G[u][v]<d[v]){
    25. 				d[v]=d[u]+G[u][v];
    26. 				pre[v]=u;
    27. 			}
    28. 		}
    29. 	}
    30. }

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

    1. void dfs(int s,int v){//s为起点，v为当前访问的顶点 
    2. 	if(v==s){
    3. 		printf("%d\n",s);
    4. 		return;
    5. 	}
    6. 	dfs(s,pre[v]);
    7. 	printf("%d\n",v);
    8. }

    进阶--标尺增多

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

    （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] 

    1. for(int v=0;v<n;v++){
    2. 	if(vis[v]==false&&G[u][v]!=INF){
    3. 		if(d[u]+G[u][v]<d[v]){
    4. 			d[v]=d[u]+G[u][v];
    5. 			c[v]=c[u]+cost[u][v];
    6. 		}
    7. 		else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
    8. 		     c[v]=c[u]+cost[u][v];
    9. 		}
    10. 	}
    11. }

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

    1. for(int v=0;v<n;v++){
    2. 	if(vis[v]==false&&G[u][v]!=INF){
    3. 		if(d[u]+G[u][v]<d[v]){
    4. 			d[v]=d[u]+G[u][v];
    5. 			w[v]=w[u]+weight[v];
    6. 		}
    7. 		else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
    8. 			w[v]=w[u]+weight[v];
    9. 		}
    10. 	}
    11. }

    （3）求最短路径条数。只需要增加一个数组num[]，令从起点s到达顶点u的最短路径条数为num[u]，初始化时只有num[s]=1、其余num[u]均为0.这样就可以在d[u]+G[u][v] 

    1. for(int v=0;v<n;v++){
    2. 	if(vis[v]==false&&G[u][v]!=INF){
    3. 		if(d[u]+G[u][v]<d[v]){
    4. 			d[v]=d[u]+G[u][v];
    5. 			num[v]=num[u];
    6. 		}
    7. 		else if(d[u]+G[u][v]==d[v]){
    8. 			num[v]+=num[u];
    9. 		}
    10. 	}
    11. }

    例题

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

    1. #include<iostream>
    2. #include<cstring>
    3. #include<algorithm>
    4. using namespace std;
    5. const int maxn=510;
    6. const int INF=1000000000;
    7. int n,m,st,ed,G[maxn][maxn],weight[maxn];//顶点数，边数，起点，终点
    8. int d[maxn],w[maxn],num[maxn];
    9. bool vis[maxn]={false};
    10. void dijkstra(int s){
    11. 	fill(d,d+maxn,INF);
    12. 	memset(num,0,sizeof(num));
    13. 	memset(w,0,sizeof(w));
    14. 	d[s]=0;
    15. 	w[s]=weight[s];
    16. 	num[s]=1;
    17. 	for(int i=0;i<n;i++){
    18. 		int u=-1,MIN=INF;
    19. 		for(int j=0;j<n;j++){
    20. 			if(vis[j]==false&&d[j]<MIN){
    21. 				u=j;
    22. 				MIN=d[j];
    23. 			}
    24. 		}
    25. 		if(u==-1){
    26. 			return;
    27. 		}
    28. 		vis[u]=true;
    29. 		for(int v=0;v<n;v++){
    30. 			if(vis[v]==false&&G[u][v]!=INF){
    31. 				if(d[u]+G[u][v]<d[v]){
    32. 					d[v]=d[u]+G[u][v];
    33. 					w[v]=w[u]+weight[v];
    34. 					num[v]=num[u];
    35. 				}
    36. 				else if(d[u]+G[u][v]==d[v]){
    37. 					if(w[u]+weight[v]>w[v]){
    38. 						w[v]=w[u]+weight[v];
    39. 					}
    40. 					num[v]+=num[u];
    41. 				}
    42. 			}
    43. 		}
    44. 	}
    45. }
    46. int main(){
    47. 	cin>>n>>m>>st>>ed;
    48. 	for(int i=0;i<n;i++){
    49. 		cin>>weight[i];
    50. 	}
    51. 	int u,v;
    52. 	fill(G[0],G[0]+maxn*maxn,INF);
    53. 	for(int i=0;i<m;i++){
    54. 		cin>>u>>v;
    55. 		cin>>G[u][v];
    56. 		G[v][u]=G[u][v];
    57. 	}
    58. 	dijkstra(st);
    59. 	cout<<num[ed]<<" "<<w[ed]<<endl;
    60. 	return 0;
    61. }

    升级方法

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

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

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

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

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

    接下来就是考虑更新d[v]的过程中pre数组的变化。首先，如果d[u]+G[u][v] 

    1. if(d[u]+G[u][v]<d[v]){
    2. 	d[v]=d[u]+G[u][v];
    3. 	pre[v].clear();
    4. 	pre[v].push_back(u);
    5. }

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

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

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

    1. vector<int> pre[maxn];
    2. void dijkstra(int s){
    3. 	fill(d,d+maxn,INF);
    4. 	d[s]=0;
    5. 	for(int i=0;i<n;i++){
    6. 		int u=-1,MIN=INF;
    7. 		for(int j=0;j<n;j++){
    8. 			if(vis[j]==false&&d[j]<MIN){
    9. 				u=j;
    10. 				MIN=INF;
    11. 			}
    12. 		}
    13. 		if(u==-1){
    14. 			return;
    15. 		}
    16. 		vis[u]=true;
    17. 		for(int v=0;v<n;v++){
    18. 			if(vis[v]==false&&G[u][v]!=INF){
    19. 				if(d[u]+G[u][v]<d[v]){
    20. 					d[v]=d[u]+G[u][v];
    21. 					pre[v].clear();
    22. 					pre[v].push_back(u);
    23. 				}
    24. 				else if(d[u]+G[u][v]==d[v]){
    25. 					pre[v].push_back(u);
    26. 				}
    27. 			}
    28. 		}
    29. 	}
    30. }

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

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

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

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

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

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

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

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

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

    1. int optValue;
    2. vector<int> pre[maxn];
    3. vector<int> path,tempPath;
    4. void dfs(int v){
    5. 	if(v==st){
    6. 		tempPath.push_back(v);
    7. 		int value;
    8. 		if(value优于optvalue){
    9. 			optvalue=value;
    10. 			path=tempPath;
    11. 		}
    12. 		tempPath.pop_back();
    13. 		return;
    14. 	}
    15. 	tempPath.push_back(v);
    16. 	for(int i=0;i<pre[v].size();i++){
    17. 		dfs(pre[v][i]);
    18. 	}
    19. 	tempPath.pop_back();
    20. }

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

    1. //边权之和 
    2. int value=0;
    3. for(int i=tempPath.size()-1;i>0;i--){
    4. 	int id=tempPath[i],idNext=tempPath[i-1];
    5. 	value+=V[id][idNext];
    6. }
    7. //点权之和 
    8. int value=0;
    9. for(int i=tempPath.size()-1;i>=0;i--){
    10. 	int id=tempPath[i];
    11. 	value+=w[id]; 
    12. }

    最后指出，如果需要同时计算最短路径的条数，那么既可以按之前的做法在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。代码如下：

    1. if(vis[v]==false&&G[u][v]!=INF){
    2. 	if(d[u]+G[u][v]<d[v]){
    3. 		d[v]=d[u]+G[u][v];
    4. 		c[v]=c[u]+cost[u][v];
    5. 		pre[v]=u;
    6. 	}
    7. 	else if(d[u]+G[u][v]==d[u]){
    8. 		if(c[u]+cost[u][v]<c[v]){
    9. 			c[v]==c[u]+cost[u][v];
    10. 			pre[v]=u;
    11. 		}
    12. 	}
    13. }

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

    1. if(v==st){
    2. 	tempPath.push_back(v);
    3. 	int tempCost=0;
    4. 	for(int i=tempPath.size()-1;i>0;i--){
    5. 		int id=tempPath[i],idNext=tempPath[i-1];
    6. 		tempCost+=cost[id][idNext];
    7. 	}
    8. 	if(tempCost<minCost){
    9. 		minCost=tempCost;
    10. 		path=tempPath;
    11. 	}
    12. 	tempPath.pop_back();
    13. 	return;
    14. }

    完整代码

    （1）dijkstra算法

    1. #include<iostream>
    2. #include<cstring>
    3. #include<algorithm>
    4. using namespace std;
    5. const int maxn=510;
    6. const int INF=1000000000;
    7. int n,m,st,ed,G[maxn][maxn],cost[maxn][maxn];
    8. int d[maxn],c[maxn],pre[maxn];
    9. bool vis[maxn]={false};
    10. void dijkstra(int s){
    11. 	fill(d,d+maxn,INF);
    12. 	fill(c,c+maxn,INF);
    13. 	for(int i=0;i<n;i++){
    14. 		pre[i]=i;
    15. 	}
    16. 	d[s]=0;
    17. 	c[s]=0;
    18. 	for(int i=0;i<n;i++){
    19. 		int u=-1,MIN=INF;
    20. 		for(int j=0;j<n;j++){
    21. 			if(vis[j]==false&&d[j]<MIN){
    22. 				u=j;
    23. 				MIN=d[j];
    24. 			}
    25. 		}
    26. 		if(u==-1){
    27. 			return;
    28. 		}
    29. 		vis[u]=true;
    30. 		for(int v=0;v<n;v++){
    31. 			if(vis[v]==false&&G[u][v]!=INF){
    32. 				if(d[u]+G[u][v]<d[v]){
    33. 					d[v]=d[u]+G[u][v];
    34. 					c[v]=c[u]+cost[u][v];
    35. 					pre[v]=u;
    36. 				}
    37. 				else if(d[u]+G[u][v]==d[v]){
    38. 					if(c[u]+cost[u][v]<c[v]){
    39. 						c[v]=c[u]+cost[u][v];
    40. 						pre[v]=u;
    41. 					}
    42. 				}
    43. 			}
    44. 		}
    45. 	}
    46. }
    47. void dfs(int v){
    48. 	if(v==st){
    49. 		cout<<v<<" ";
    50. 		return;
    51. 	}
    52. 	dfs(pre[v]);
    53. 	cout<<v<<" ";
    54. }
    55. int main(){
    56. 	cin>>n>>m>>st>>ed;
    57. 	int u,v;
    58. 	fill(G[0],G[0]+maxn*maxn,INF);
    59. 	for(int i=0;i<m;i++){
    60. 		cin>>u>>v;
    61. 		cin>>G[u][v]>>cost[u][v];
    62. 		G[v][u]=G[u][v];
    63. 		cost[v][u]=cost[u][v];
    64. 	}
    65. 	dijkstra(st);
    66. 	dfs(ed);//打印路径 
    67. 	cout<<d[ed]<<" "<<c[ed]<<endl;
    68. 	return 0;
    69. }

    （2）dijkstra+dfs

    1. #include<iostream>
    2. #include<cstring>
    3. #include<vector>
    4. #include<algorithm>
    5. using namespace std;
    6. const int maxn=510;
    7. const int INF=1000000000;
    8. int n,m,st,ed,G[maxn][maxn],cost[maxn][maxn];
    9. int d[maxn],minCost=INF;
    10. bool vis[maxn]={false};
    11. vector<int> pre[maxn];
    12. vector<int> tempPath,path;
    13. void dijkstra(int s){
    14. 	fill(d,d+maxn,INF);
    15. 	d[s]=0;
    16. 	for(int i=0;i<n;i++){
    17. 		int u=-1,MIN=INF;
    18. 		for(int j=0;j<n;j++){
    19. 			if(vis[j]==false&&d[j]<MIN){
    20. 				u=j;
    21. 				MIN=d[j];
    22. 			}
    23. 		}
    24. 		if(u==-1){
    25. 			return;
    26. 		}
    27. 		vis[u]=true;
    28. 		for(int v=0;v<n;v++){
    29. 			if(vis[v]==false&&G[u][v]!=INF){
    30. 				if(d[u]+G[u][v]<d[v]){
    31. 					d[v]=d[u]+G[u][v];
    32. 					pre[v].clear();
    33. 					pre[v].push_back(u);
    34. 				}
    35. 				else if(d[u]+G[u][v]==d[v]){
    36. 					pre[v].push_back(u);
    37. 				}
    38. 			}
    39. 		}
    40. 	}
    41. }
    42. void dfs(int v){
    43. 	if(v==st){
    44. 		tempPath.push_back(v);
    45. 		int tempCost=0;
    46. 		for(int i=tempPath.size()-1;i>0;i--){
    47. 			int id=tempPath[i],idNext=tempPath[i-1];
    48. 			tempCost+=cost[id][idNext];
    49. 		}
    50. 		if(tempCost<minCost){
    51. 			minCost=tempCost;
    52. 			path=tempPath;
    53. 		}
    54. 		tempPath.pop_back();
    55. 		return;
    56. 	}
    57. 	tempPath.push_back(v);
    58. 	for(int i=0;i<pre[v].size();i++){
    59. 		dfs(pre[v][i]);
    60. 	}
    61. 	tempPath.pop_back();
    62. }
    63. int main(){
    64. 	cin>>n>>m>>st>>ed;
    65. 	int u,v;
    66. 	fill(G[0],G[0]+maxn*maxn,INF);
    67. 	fill(cost[0],cost[0]+maxn*maxn,INF);
    68. 	for(int i=0;i<m;i++){
    69. 		cin>>u>>v;
    70. 		cin>>G[u][v]>>cost[u][v];
    71. 		G[v][u]=G[u][v];
    72. 		cost[v][u]=cost[u][v];
    73. 	}
    74. 	dijkstra(st);
    75. 	dfs(ed);
    76. 	for(int i=path.size()-1;i>=0;i--){
    77. 		cout<<path[i]<<" ";
    78. 	}
    79. 	cout<<d[ed]<<" "<<minCost<<endl;
    80. 	return 0;
    81. }
  • 相关阅读:
    Windows 10外接屏性能挖掘
    API设计中性能提升的10个建议
    Session会话追踪的实现机制
    2022全球数字经济大会开元之境 金谷诺亚-李刚：数字藏品业态
    Content-Security-Policy（CSP）的内容构成。
    【c++设计模式之桥接模式】分析及示例
    Vue3 源码阅读（9）：渲染器 —— diff 算法
    只有天空才是你的极限，我们热爱探索的过程并沉浸其中丨图数据库 TiMatch 团队访谈
    javascript中this的指向问题
    在Linux系统上检测GPU显存和使用情况
  • 原文地址：https://blog.csdn.net/m0_72674633/article/details/139583641