Dijsktra

• 适用条件：边权为正
• 相关应用：求最短路，打印最短路路径

1. 初始化（如果求最短路求初始化所有节点为INF，所求的起点的为0）
2. 找出一个未被标记的、 $d\left[x\right]$d[x]最小的节点 $x$x，然后标记结点 $x$x。
3. 扫描节点 $x$x的所有出边 $(x,y,z)$(x,y,z)，若 $d\left[y\right]>d\left[x\right]+z$d[y]>d[x]+z则更新 $d\left[y\right]=d\left[x\right]+z$d[y]=d[x]+z。
4. 重复上述2~3两个步骤，直到所有节点都被标记。

djisktra+邻接矩阵 $O\left(n^2\right)$O(n2)

const int N = 3005;

int n,m,e[N][N];
bool v[N];

void Dji(const int &s,const int &n){
	memset(v,0,sizeof(v));//标记
	memset(d,INF,sizeof(d));
	d[s]=0;
	for(int i=1;i<=n;i++){
		int x=-1;
		//找未标记节点中d最小的
		for(int j=1;j<=n;j++) if(!v[j] && (x==-1 || d[j]<d[x])) x=j;
		v[x]=true;
		//利用x作为中转点更新其他结点
		for(int j=1;j<=n;j++) if(d[j]>d[x]+e[x][k]) d[j]=d[x]+e[x][k];
	}
}

上述代码找未标记节点中 $d$d最小的可以使用堆优化维护，用 $O\left(logn\right)$O(logn)的时间获取最小值并从堆中删除，用 $O\left(logn\right)$O(logn)的时间执行一条边的扩展和更新。

djisktra+堆优化 $O\left(\right(m+n\left)logn\right)$O((m+n)logn)

const int N = 1e5 + 5;

struct edge{int to,cost;};
int n,m,d[N];
vector<edge>G[N];//由于vecotr默认的比较方式是先比较first再比较second所以放入的时候应当放入{d[i],i}
bool v[N];

void Dji(const int &s,const int &n){
	priority_queue<P,vector<P>,greater<P> >q;
	memset(v,0,sizeof(v));
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	q.push({0,s});
	while(!q.size()){
		int t=q.top().second; q.pop();
		if(v[t]) continue;
		v[t]=true;
		for(int i=0;i<G[t].size();i++){
			edge e=G[t][i];
			if(d[e.to]>d[t]+e.cost){
				d[e.to]=d[t]+e.cost;
				q.push({d[e.to],e.to});
			}
		}
	}
}

上述代码还可以优化空间复杂度，去掉 $v$v数组。

struct edge{int to,cost;};
vector<edge>G[N];
ll d[N];

void Dij(const int& s,const int& V,ll *d){
	priority_queue<P,vector<P>,greater<P> >q;
	fill(d,d+V+1,INF);
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		P t=q.top();q.pop();
		int v=t.se;
		if(d[v]<t.fi) continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				q.push({d[e.to],e.to});
			}
		}
	}
}

由于vector的常数较大，对于一些卡vector的题目，可以使用链式前向星来代替vector实现。
待更

在原来的问题基础上要求输出最短路路径，则可将以下代码

if(d[e.to]>d[x]+e.cost){
	d[e.to]=d[x]+e.cost;
	q.push({d[e.to],e.to});
}

if(d[e.to]>d[x]+e.cost){
	d[e.to]=d[x]+e.cost;
	path[e.to]=x;
	q.push({d[e.to],e.to});
}

这样存的是倒序所以要改为正序

1. 利用栈FILO，从终点开始依次放入，再取出即可。

void print(const int &e){//输入终点倒序遍历放入栈中再正序输出
    //路径不存在
	if(d[e]>=INF) return;
	stack<int>q;
	int j=e;
	while(j!=-1){
		q.push(j);
		j=path[j];
	}
	while(!q.empty()){
		cout<<q.top()<<" ";
		q.pop();
	}
	cout<<'\n';
}

2. 利用reverse函数

void print(int e){
	if(d[e]>=INF) return;
	vector<int>prev;
	for(;e!=-1;e=prev[e]) prev.push_back(e);
	reverse(prev.begin(),prev.end());
	for(auto c:prev) cout<<c<<" ";
}

P4779

题意

输入n,m,s,分别代表结点的个数，路径的数量，起点。
输入m行数据，每行为 $u_i,v_i,w_i$ui​,vi​,wi​表示第 $i$i条路由 $u_i\to v_i$ui​→vi​权值为 $w_i$wi​。
要求输出s出发到1到n所有点的最短路为多少。
$1\le n\le 1e51\le m\le 2e5$1≤n≤1e51≤m≤2e5

思路

dijsktra+堆优化

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int n,m,s;

struct edge{int to,cost;};
vector<edge>G[N];
int d[N];

void dijkstra(const int& s,const int& V){
	priority_queue<P,vector<P>,greater<P> >q;
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		P t=q.top();q.pop();
		int v=t.se;
		if(d[v]<t.fi) continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				q.push({d[e.to],e.to});
			}
		}
	}
}

void print(int n){
	for(int i=1;i<=n;i++){
		if(d[i]<INF) cout<<d[i]<<" ";
		else cout<<(1<<31)-1<<" ";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra(s,n);
	print(n);
	return 0;
}

CF20C

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const ll INF  = 0x3f3f3f3f3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int n,m,s;

struct edge{int to,cost;};
vector<edge>G[N];
ll d[N];
int path[N];

void dijkstra(const int& s,const int& V){
	priority_queue<P,vector<P>,greater<P> >q;
	memset(d,0x3f,sizeof(d));
	memset(path,-1,sizeof(path));
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		P t=q.top();q.pop();
		int v=t.se;
		if(d[v]<t.fi) continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				path[e.to]=v;
				q.push({d[e.to],e.to});
			}
		}
	}
}

void print(int n){
	if(d[n]>=INF){
		cout<<-1<<'\n';
		return;
	}
	stack<int>q;
	int i=n;
	int j=i;
	while(path[j]!=-1){
		q.push(j);
		j=path[j];
	}
	q.push(j);
	while(!q.empty()){
		cout<<q.top()<<" ";
		q.pop();
	}
	cout<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dijkstra(1,n);
	print(n);
	return 0;
}