跳到主要内容

最短路

参考资料​

最短路​

算法对比​

nn 代表图的点数，mm 代表图的边数。

算法名称时间复杂度最短路类型负权图
Floyd 算法O(n3)O(n^3)全源最短路能
Bellman–Ford 算法O(nm)O(nm)单源最短路能
Dijkstra 算法O(mlog⁡m)O(m\log m)单源最短路否
Johnson 算法O(nmlog⁡m)O(nm\log m)全源最短路能

Floyd 算法​

int a[N][N];
void floyd(int n)
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	}
}

Bellman–Ford 算法​

SPFA（Shortest Path Faster Algorithm）是 Bellman–Ford 算法的一种实现。

vector<pair<int,int>> G[N];
int dis[N],cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(dis[v]<=dis[u]+w)continue;
			dis[v]=dis[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}

Dijkstra 算法​

vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	priority_queue<pair<int,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}

Johnson 算法​

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

using ll=long long;
const int N=3005;
const ll inf=0x3f3f3f3f3f3f3f3f;
vector<pair<int,int>> G[N];
ll h[N],dis[N];
int cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(h,0x3f,sizeof h);
	h[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(h[v]<=h[u]+w)continue;
			h[v]=h[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pair<ll,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++)G[0].push_back({i,0});
	if(!spfa(0,n+1))
	{
		cout<<-1<<'\n';
		return 0;
	}
	for(int u=1;u<=n;u++)for(auto &[v,w]:G[u])w+=h[u]-h[v];
	for(int i=1;i<=n;i++)
	{
		dijkstra(i);
		ll ans=0;
		for(int j=1;j<=n;j++)
		{
			ans+=j*(dis[j]==inf?1000000000ll:dis[j]+h[j]-h[i]);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

差分约束​

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

const int inf=0x3f3f3f3f;
const int N=5005;
vector<pair<int,int>> G[N];
int dis[N],cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(dis[v]<=dis[u]+w)continue;
			dis[v]=dis[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n+1)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)G[0].push_back({i,0});
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[v].push_back({u,w});
	}
	if(!spfa(0,n))
	{
		cout<<"NO"<<'\n';
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<' ';
	}
	return 0;
}

例题​

洛谷 B3647 【模板】Floyd​

洛谷 B3647 【模板】Floyd

给定一张 nn 个点 mm 条边的无向图，求所有点对 (i,j)(i,j) 之间的最短路径长度。（n≤100,m≤4500n\le100,m\le4500）

代码（1）
#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=105;
int a[N][N];
void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=i==j?0:inf;
		}
	}
}
void floyd(int n)
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	init(n);
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u][v]=min(a[u][v],w);
		a[v][u]=min(a[v][u],w);
	}
	floyd(n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

洛谷 P3371 【模板】单源最短路径（弱化版）​

洛谷 P3371 【模板】单源最短路径（弱化版）

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

代码（2）
#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=10005;
vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	priority_queue<pair<int,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,s;
	cin>>n>>m>>s;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<(dis[i]!=inf?dis[i]:INT_MAX)<<' ';
	}
	return 0;
}

洛谷 P4779 【模板】单源最短路径（标准版）​

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

给定一张 nn 个点 mm 条有向边的非负权图，求从 ss 出发到每个点的距离。（n≤105,m≤2×105n\le10^5,m\le2\times10^5）

代码（1）
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	priority_queue<pair<int,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,s;
	cin>>n>>m>>s;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<' ';
	}
	return 0;
}

洛谷 P5905 【模板】全源最短路（Johnson）​

洛谷 P5905 【模板】全源最短路（Johnson）

给定一个包含 nn 个结点和 mm 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。

代码（1）
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=3005;
const ll inf=0x3f3f3f3f3f3f3f3f;
vector<pair<int,int>> G[N];
ll h[N],dis[N];
int cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(h,0x3f,sizeof h);
	h[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(h[v]<=h[u]+w)continue;
			h[v]=h[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pair<ll,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++)G[0].push_back({i,0});
	if(!spfa(0,n+1))
	{
		cout<<-1<<'\n';
		return 0;
	}
	for(int u=1;u<=n;u++)for(auto &[v,w]:G[u])w+=h[u]-h[v];
	for(int i=1;i<=n;i++)
	{
		dijkstra(i);
		ll ans=0;
		for(int j=1;j<=n;j++)
		{
			ans+=j*(dis[j]==inf?1000000000ll:dis[j]+h[j]-h[i]);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

洛谷 P3385 【模板】负环​

洛谷 P3385 【模板】负环

给定一个 nn 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

代码（1）
#include <bits/stdc++.h>
using namespace std;

const int N=2005;
vector<pair<int,int>> G[N];
int dis[N],cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(dis,0x3f,sizeof dis);
	memset(cnt,0,sizeof cnt);
	memset(vis,0,sizeof vis);
	dis[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(dis[v]<=dis[u]+w)continue;
			dis[v]=dis[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		while(m--)
		{
			int u,v,w;
			cin>>u>>v>>w;
			G[u].push_back({v,w});
			if(w>=0)G[v].push_back({u,w});
		}
		cout<<(spfa(1,n)?"NO":"YES")<<'\n';
		for(int i=1;i<=n;i++)G[i].clear();
	}
	return 0;
}

洛谷 P5960 【模板】差分约束​

洛谷 P5960 【模板】差分约束

给出一组包含 mm 个不等式，有 nn 个未知数的形如：

{xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\ x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots \\ x_{c_m} - x_{c'_m}\leq y_m \end{cases}

的不等式组，求任意一组满足这个不等式组的解。

代码（1）
#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=5005;
vector<pair<int,int>> G[N];
int dis[N],cnt[N];
bool vis[N];
bool spfa(int s,int n)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto [v,w]:G[u])
		{
			if(dis[v]<=dis[u]+w)continue;
			dis[v]=dis[u]+w;
			cnt[v]=cnt[u]+1;
			if(cnt[v]>=n+1)return 0;
			if(!vis[v]){q.push(v);vis[v]=1;}
		}
	}
	return 1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)G[0].push_back({i,0});
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[v].push_back({u,w});
	}
	if(!spfa(0,n))
	{
		cout<<"NO"<<'\n';
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<' ';
	}
	return 0;
}