最短路

参考资料

算法对比

最短路（Shortest Path）问题求图中两点间边权和最小的路径，分单源（一点到其余各点）与全源（所有点对之间）两类。下表对比常用算法，其中 $n$ 代表图的点数， $m$ 代表图的边数。

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

Floyd 算法

Floyd 基于动态规划求全源最短路。外层枚举中转点 $k$ ，用 $a_{i,k}+a_{k,j}$ 松弛 $a_{i,j}$ ；枚举完所有 $k$ 后 $a_{i,j}$ 即为最短路。 $k$ 必须放在最外层循环。它能处理负权边（无负环），实现简单，时间复杂度为 $O(n^3)$ 。

172 Bcpp
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 算法

Bellman–Ford 通过反复松弛所有边求单源最短路。最短路至多含 $n-1$ 条边，故 $n-1$ 轮松弛后收敛，时间复杂度为 $O(nm)$ 。它能处理负权边；若第 $n$ 轮仍可松弛，则图中存在负环。

SPFA（Shortest Path Faster Algorithm）是其队列优化：仅把被更新的点入队参与下一轮松弛，随机图上更快，但最坏仍为 $O(nm)$ ，易被特殊数据卡。下面的实现用 $\mathrm{cnt}_v$ 记录最短路边数，达到 $n$ 即判定负环。

407 Bcpp
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 算法

Dijkstra 求非负权图的单源最短路，基于贪心：每次取出当前距离最小且未确定的点，用它松弛邻居，已确定的点距离不再更改。用优先队列维护候选点，时间复杂度为 $O(m\log m)$ 。它不能处理负权边。下面用大根堆存 $-\mathrm{dis}$ 来模拟小根堆。

368 Bcpp
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 算法

Johnson 求含负权边（无负环）图的全源最短路。先建虚拟源点 $0$ 向每个点连零权边，用 SPFA 求出势能 $h_u$ ；再将每条边 $(u,v)$ 重赋权为 $w+h_u-h_v$ ，新权非负且不改变最短路结构。然后以每个点为源跑 Dijkstra，最后把距离还原为 $\mathrm{dis}_{i,j}+h_j-h_i$ 。若虚拟源点的 SPFA 发现负环则无解。时间复杂度为 $O(nm\log m)$ 。

1.32 KBcpp
#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;
}

传递闭包

传递闭包判断每对点之间是否可达。沿用 Floyd 框架，把松弛换成按位或与按位与：若 $i$ 经 $k$ 可达 $j$ ，则 $i$ 可达 $j$ （对应代码 a[i][j]|=a[i][k]&a[k][j]）。时间复杂度为 $O(n^3)$ ，可用 bitset 优化到 $O(n^3/w)$ 。

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

const int N=105;
bool a[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]|=a[i][k]&a[k][j];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

差分约束

差分约束系统由若干形如 $x_u-x_v\le w$ 的不等式组成，求一组可行解。把每个约束 $x_u-x_v\le w$ 建成一条 $v\to u$ 权为 $w$ 的边，则从虚拟源点 $0$ 向所有点连零权边后跑 SPFA，得到的 $\mathrm{dis}_i$ 就是一组可行解 $x_i$ 。若存在负环则无解。

818 Bcpp
#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

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

洛谷 B3611 【模板】传递闭包

给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

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

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

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

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

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

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

洛谷 P3385 【模板】负环

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

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

洛谷 P5960 【模板】差分约束

给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

\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}

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

参考资料​

算法对比​

Floyd 算法​

Bellman–Ford 算法​

Dijkstra 算法​

Johnson 算法​

传递闭包​

差分约束​

例题​