【dijkstra算法】

推荐视频链接
推荐好文
注：只是新手的笔记，慎看！！！欢迎大佬指错

最短路径算法是图论中一类 重要算法，其功能就如名字一样——求解点与点之间最短距离。
而dijkstra算法则是其重要且基本的手段之一

求如图 1 到 2 的最短路程及路径

dijstra思路：

• 开三个数组，分别表示
  - 节点链接关系和边权 e
  - 从起点到某点的最短距离 d
  - 判定数组 vis
• 初始设 d 为无穷大
• 建一个小根堆，其内部存一个二元数组【该点到起点距离，该点】
• 如果题目要求记录路径，则再开一个pre数组，
  • pre[ u ] = v，表u的下一个数字是v
• 遍历堆 q ，每次选择距离起点最短的数字，遍历他的相连节点
• 对于第 v 个数字，d【v】=min( d【v】，d【u】+ 边权）

注意：

我们设堆时先建一个大根堆，但是存距离时，我们存其相反数，也能有小根堆的效果，还不用重构

代码：

#include <bits/stdc++.h>
#define int long long
#define all(x) begin(x)+1,end(x)
#define double long double
using namespace std;

struct node
{
	int v,w;
};
const int N=1e5+5;

vector <node> e[N];
bool vis[N];
int d[N];
priority_queue <pair<int,int>> q;//大根堆存负值变小根堆
int n,m; 
int inf=1e18;
int pre[N];//路径

void dijkstra(int s)//s起点
{
	for(int i=1;i<=n;i++) d[i]=inf;//无穷大
	d[s]=0;
	q.push({0,s});
	while(q.size())
	{
		auto t=q.top();
		q.pop();
		int u=t.second;//u为当前节点
		if(vis[u]) continue;//如果已被标记，则说明已找到最短路径
		vis[u]=true;
		for(auto eg:e[u] )
		{
			int v=eg.v,w=eg.w;
			if(d[v]>d[u]+w)//如果有更优解，则用更优解
			{
				d[v]=d[u]+w;
				pre[v]=u;
				q.push({-d[v],v});
			}
		}
	}
}

void prinf(int t)//递归输出路径
{
	if(t==0) return;
	prinf(pre[t]);
	cout<<t<<" ";
}

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});//看题目要求是单向还是无向图
		e[v].push_back({u,w});
	}
	dijkstra(1);
	//cout<<d[n];
	prinf(n);
}
 
signed main()
{
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
		cout<<endl;
	}
	
	return 0;
}