【算法教程】【C/C++】单源最短路径——程序设计思路与代码实现

前言

        最短路径是求在一张有向图中,起点到终点的距离。求最短路径的方法有很多,如SPFA、floyd、dijkstra等,今天我们学习dijkstra的思路与代码,其优点是时间复杂度和空间复杂度都很低,缺点是不能处理重边。


程序设计思路

       dijkstra基于贪心实现,又有点类似DP,其思路大致如下:先把起点到所有点的距离都设为inf(一个很大的数),然后在所有与起点相连接的边中找到最短的一条,将这个新的点作为起点,并更新从起点出发到这个点的最短距离,直到找到终点。这个逐步更新的操作被称为松弛。


代码实现

IMG_20240831_080804.png

        洛谷上还有一道数据随机的模板题,这题专卡SPFA,但对我们的dijskla没有影响,下面是代码:

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

struct Edge{//结构体用来存一条边的起点、终点、长度
	int to,dis,ne;
}edge[2000005];

int n,m,s,cnt,dist[2000005],head[2000005],x,y,z;//n、m、s如题意,cnt用来计数,dist存起点到各个点的最短距离
bool visit[2000005];//类似BFS中记录已经访问的点

void Add_edge(int from,int to,int w){//加入数组
	edge[++cnt].to=to;
	edge[cnt].dis=w;
	edge[cnt].ne=head[from];
	head[from]=cnt;
}

struct node{
	int id,dis;
	bool operator <(const node &a)const{ return a.dis<dis; }//优先队列升序排序
};
void dijkstra(){
	priority_queue<node> q;
	q.push(node{s,0});
	for(int i=1;i<=n;i++) dist[i]=inf;
	dist[s]=0;
	while(!q.empty()){
		node a=q.top();
		q.pop();//类似BFS的队列
		int now=a.id;
		if(visit[now]) continue;
		visit[now]=1;
		for(int i=head[now];i;i=edge[i].ne){//查所有边
			int j=edge[i].to;
			if(dist[now]+edge[i].dis<dist[j]){//判断走的这条路是不是比原来的更短
				dist[j]=dist[now]+edge[i].dis;
				q.push(node{j,dist[j]});
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		Add_edge(x,y,z);
	}
	dijkstra();
	for(int i=1;i<=n;i++) printf("%d ",dist[i]);
	return 0;
}


结语

        dijkstra不能处理重边,这一点在选择方法时需要注意。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/108.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/108.html

标签: C++算法基础
分享给朋友:
返回列表

上一篇:对本站内容的说明&对日记站的说明

没有最新的文章了...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。