最短路算法流程

CJY2025/7/27大约 7 分钟

最短路算法流程

Floyd

Floyd-Warshall 算法

初始化距离矩阵 $\text{dist}$ $dist$ ：
- 对于任意 $i,j$ $i, j$ ：
  - 若 $i = j$ 则 $\text{dist}_{i,j} = 0$
  - 否则若存在边 $i \to j$ ，则 $\text{dist}_{i,j} = w(i,j)$
  - 否则 $\text{dist}_{i,j} = \infty$
遍历所有中间点 $k$ $k$ （ $1 \leq k \leq n$ $1 \leq k \leq n$ ）：
- 对每个 $i$ $i$ （ $1 \leq i \leq n$ $1 \leq i \leq n$ ）：
  - 对每个 $j$ $j$ （ $1 \leq j \leq n$ $1 \leq j \leq n$ ）：
    - 如果 $\text{dist}_{i,k} + \text{dist}_{k,j} < \text{dist}_{i,j}$ $dist_{i, k} + dist_{k, j} < dist_{i, j}$ ：
      - $\text{dist}_{i,j} \gets \text{dist}_{i,k} + \text{dist}_{k,j}$
最终 $\text{dist}_{i,j}$ 存储 $i$ 到 $j$ 的最短路径长度

全源最短路径
能处理负权边
时间复杂度： $O(n^3)$

朴素 Dijkstra

朴素 Dijkstra 算法

初始化：
- $\text{dist}_s = 0$ ，对于任意 $u \neq s$ ， $\text{dist}_u = \infty$
- 集合 $S \gets \emptyset$ （已确定最短路径的点）
当 $S \neq V$ $S \neq = V$ （ $V$ $V$ 为节点集）时：
- 选取 $u \notin S$ 且 $\text{dist}_u$ 最小
- 在 $S$ 中加入 $u$
- 对 $u$ $u$ 的每个邻居 $v$ $v$ ：
  - 如果 $\text{dist}_u + w(u,v) < \text{dist}_v$ $dist_{u} + w (u, v) < dist_{v}$ ：
    - $\text{dist}_v \gets \text{dist}_u + w(u,v)$

单源最短路径
不能处理负权边
时间复杂度： $O(n^2)$

堆优化 Dijkstra

初始化：
- $\text{dist}_s = 0$ ，对于任意 $u \neq s$ ， $\text{dist}_u = \infty$
- 小根堆 $Q$ 插入 $(s, 0)$
- 对于任意 $u$ ， $\text{visit}_u \gets \text{false}$
当 $Q$ $Q$ 非空时：
- 弹出 $Q$ 中 $\text{dist}_u$ 最小的 $u$
- 如果 $\text{visit}_u = \text{true}$ $visit_{u} = true$ ：
  - 跳过
- 否则：
  - $\text{visit}_u \gets \text{true}$
- 对 $u$ $u$ 的每个邻居 $v$ $v$ ：
  - 如果 $\text{dist}_u + w(u,v) < \text{dist}_v$ $dist_{u} + w (u, v) < dist_{v}$ ：
    - $\text{dist}_v \gets \text{dist}_u + w(u,v)$
    - 在 $Q$ 中加入 $(v, \text{dist}_v)$

单源最短路径
不能处理负权边
时间复杂度： $O(m \log n)$

Bellman-Ford

Bellman-Ford 算法

初始化：
- $\text{dist}_s = 0$ ，对于任意 $u \neq s$ ， $\text{dist}_u = \infty$
迭代 $n-1$ $n - 1$ 次（ $n = |V|$ $n = ∣ V ∣$ ）：
- 对每条边 $(u,v,w)$ $(u, v, w)$ ：
  - 如果 $\text{dist}_u + w(u,v) < \text{dist}_v$ $dist_{u} + w (u, v) < dist_{v}$ ：
    - $\text{dist}_v \gets \text{dist}_u + w(u,v)$
负环检测：
- 对每条边 $(u,v,w)$ $(u, v, w)$ ：
  - 如果 $\text{dist}_u + w(u,v) < \text{dist}_v$ ，则存在负环

单源最短路径
能处理负权边
时间复杂度： $O(nm)$

SPFA

初始化：
- $\text{dist}_s = 0$ ，对于任意 $u \neq s$ ， $\text{dist}_u = \infty$
- 在 $Q$ 中加入 $s$ ， $\text{in\_queue}_s \gets \text{true}$
- 对于任意 $u \neq s$ ， $\text{in\_queue}_u \gets \text{false}$
当 $Q$ $Q$ 非空时：
- $u$ 出队， $\text{in\_queue}_u \gets \text{false}$
- 对 $u$ $u$ 的每个邻居 $v$ $v$ ：
  - 如果 $\text{dist}_u + w(u,v) < \text{dist}_v$ $dist_{u} + w (u, v) < dist_{v}$ ：
    - $\text{dist}_v \gets \text{dist}_u + w(u,v)$
    - 如果 $\text{in\_queue}_v = \text{false}$ $in_queue_{v} = false$ ：
      - $v$ 入队， $\text{in\_queue}_v \gets \text{true}$
- 若最短路包含边数 $> m$ ，则存在负环

单源最短路径
能处理负权边
时间复杂度： $O(nk)\sim O(nm)$

代码示例

Floyd

邻接矩阵

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w,f[N][N];
void init(){
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=n;i++)
		f[i][i]=0;
}
void add(int u,int v,int w){
	f[u][v]=min(f[u][v],w);
}
void solve(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for(int i=1;i<=n;i++)dis[i]=f[s][i];
}

朴素 Dijkstra

邻接表

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
vector<pair<int,int>>g[N];
bool vis[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++)g[i].clear();
	dis[s]=0;
}
void add(int u,int v,int w){
	g[u].push_back({v,w});
}
void solve(){
	for(int i=1;i<=n;i++){
		int mi=inf,u=-1;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<mi)
				mi=dis[j],u=j;
		vis[u]=1;
		for(auto v:g[u])
			if(dis[u]+v.second<dis[v.first])
				dis[v.first]=dis[u]+v.second;
	}
}

链式前向星

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
struct Edge{
	int to,w,nxt;
}edge[M];
int cnt,head[N];
void add(int u,int v,int w){
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
bool vis[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(edge,0,sizeof edge);
	memset(head,0,sizeof head);
	dis[s]=0,cnt=0;
}
void solve(){
	for(int i=1;i<=n;i++){
		int mi=inf,u=-1;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<mi)
				mi=dis[j],u=j;
		vis[u]=1;
		for(int v=head[u];v;v=edge[v].nxt)
			if(dis[u]+edge[v].w<dis[edge[v].to])
				dis[edge[v].to]=dis[u]+edge[v].w;
	}
}

堆优化 Dijkstra

邻接表

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
struct node{
	int id,dis;
	bool operator<(const node& x)const{return dis>x.dis;}
};
vector<pair<int,int>>g[N];
priority_queue<node>q;
bool vis[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++)g[i].clear();
	while(q.size())q.pop();
	dis[s]=0;
}
void add(int u,int v,int w){
	g[u].push_back({v,w});
}
void solve(){
	q.push({s,0});
	while(q.size()){
		int u=(q.top()).id;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto v:g[u])
			if(dis[u]+v.second<dis[v.first]){
				dis[v.first]=dis[u]+v.second;
				q.push({v.first,dis[v.first]});
			}
	}
}

链式前向星

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
struct Edge{
	int to,w,nxt;
}edge[M];
int cnt,head[N];
void add(int u,int v,int w){
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
struct node{
	int id,dis;
	bool operator<(const node& x)const{return dis>x.dis;}
};
vector<pair<int,int>>g[N];
priority_queue<node>q;
bool vis[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(edge,0,sizeof edge);
	memset(head,0,sizeof head);
	dis[s]=0,cnt=0;
	while(q.size())q.pop();
}
void solve(){
	q.push({s,0});
	while(q.size()){
		int u=(q.top()).id;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int v=head[u];v;v=edge[v].nxt)
			if(dis[u]+edge[v].w<dis[edge[v].to]){
				dis[edge[v].to]=dis[u]+edge[v].w;
				q.push({edge[v].to,dis[edge[v].to]});
			}
	}
}

Bellman-Ford

邻接表

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
vector<pair<int,int>>g[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)g[i].clear();
	dis[s]=0;
}
void add(int u,int v,int w){
	g[u].push_back({v,w});
}
bool solve(){
	for(int i=1;i<n;i++)
		for(int j=1;j<=n;j++)
			for(auto v:g[j])
				if(dis[j]+v.second<dis[v.first])
					dis[v.first]=dis[j]+v.second;
	for(int j=1;j<=n;j++)
		for(auto v:g[j])
			if(dis[j]+v.second<dis[v.first])
				return 1;
	return 0;
}

链式前向星

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
struct Edge{
	int to,w,nxt;
}edge[M];
int cnt,head[N];
void add(int u,int v,int w){
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(edge,0,sizeof edge);
	memset(head,0,sizeof head);
	dis[s]=0,cnt=0;
}
bool solve(){
	for(int i=1;i<n;i++)
		for(int j=1;j<=n;j++)
			for(int v=head[j];v;v=edge[v].nxt)
				if(dis[j]+edge[v].w<dis[edge[v].to])
					dis[edge[v].to]=dis[j]+edge[v].w;
	for(int j=1;j<=n;j++)
		for(int v=head[j];v;v=edge[v].nxt)
			if(dis[j]+edge[v].w<dis[edge[v].to])
				return 1;
	return 0;
}

SPFA

邻接表

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
vector<pair<int,int>>g[N];
queue<int>q;
bool inq[N];
int cnt[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(inq,0,sizeof inq);
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++)g[i].clear();
	while(q.size())q.pop();
	dis[s]=0;
}
void add(int u,int v,int w){
	g[u].push_back({v,w});
}
bool solve(){
	q.push(s);
	inq[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		if(cnt[u]>m)return 1;
		for(auto [v,w]:g[u]){
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(!inq[v])q.push(v),inq[v]=1;
			}
		}
	}
	return 0;
}

链式前向星

const int N=510,M=5010,inf=0x3f3f3f3f;
int n,m,s=1,dis[N],u,v,w;
struct Edge{
	int to,w,nxt;
}edge[M];
int tot,head[N];
void add(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
queue<int>q;
bool inq[N];
int cnt[N];
void init(){
	memset(dis,0x3f,sizeof dis);
	memset(inq,0,sizeof inq);
	memset(cnt,0,sizeof cnt);
	memset(edge,0,sizeof edge);
	memset(head,0,sizeof head);
	while(q.size())q.pop();
	dis[s]=0,tot=0;
}
bool solve(){
	q.push(s);
	inq[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		if(cnt[u]>m)return 1;
		for(int v=head[u];v;v=edge[v].nxt){
			if(dis[u]+edge[v].w<dis[edge[v].to]){
				dis[edge[v].to]=dis[u]+edge[v].w;
				cnt[edge[v].to]=cnt[u]+1;
				if(!inq[edge[v].to])q.push(edge[v].to),inq[edge[v].to]=1;
			}
		}
	}
	return 0;
}

使用示例

#include<bits/stdc++.h>
using namespace std;
/*Shortest Path Code*/
int main(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	solve();
	for(int i=1;i<=n;i++)
		cout<<(dis[i]==inf?-1:dis[i])<<'\n';
	return 0;
}

提示

Bellman-Ford、SPFA 的 solve() 函数有返回值，可以判断负环。

注意

邻接表 SPFA 代码中的 for(auto [v,w]:g[u]) 在 C++17 及以上版本才能使用。

模板题