最短路算法

Qiansui / 2023-06-26 / 原文

最短路算法
- 单源最短路-迪杰斯特拉算法

最短路算法

单源最短路-迪杰斯特拉算法

用于计算一个节点到其他所有节点的最短路径
Dijkstra 算法是贪心算法, 是一种求解非负权图上单源最短路径的算法。
基本思想是：设置一个顶点的集合S，并不断地扩充这个集合，当且仅当从源点到某个点的路径已求出时它才属于集合S。开始时S中仅有源点,调整S 集合之外的点的最短路径长度, 并从中找到当前最短路径点，将其加入到集合S,直到所有的点都在S中。
目前仅对非负权边图有效
例题：

【模板】单源最短路径（标准版）

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
typedef std::pair<ull,ull> pull;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;

const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,m,s,head[maxm],cnt,dis[maxm];
bool vis[maxm];
struct node{
	ll to,next,wei;
}p[maxm];

void add_edge(ll u,ll v, ll w){
	p[cnt].to=v;
	p[cnt].next=head[u];
	p[cnt].wei=w;
	head[u]=cnt++;
	return ;
}

void pre(int x){
	for(int i=1;i<=x;++i){
		dis[i]=inf;
		head[i]=-1;
		vis[i]=false;
	}
	return ;
}

void dij(int x){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
	q.push({0,x});
	pair<ll,ll> t;
	while(!q.empty()){
		t=q.top();
		q.pop();
		if(vis[t.second]) continue;
		vis[t.second]=true;
		dis[t.second]=t.first;
		for(int i=head[t.second];i!=-1;i=p[i].next){
			if(!vis[p[i].to]&&dis[t.second]+p[i].wei<dis[p[i].to]){
				q.push({dis[t.second]+p[i].wei,p[i].to});
			}
		}
	}
	return ;
}

void solve(){
	cnt=0;
	cin>>n>>m>>s;
	pre(n);
	for(int i=0;i<m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	dij(s);
	for(int i=1;i<=n;++i){
		cout<<dis[i]<<" \n"[i==n];
	}
	return ;
}

signed main(){
	// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}