专栏文章

最短路总结

rren_gao_zu
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioztqs8
此快照首次捕获于
2025/12/03 03:50
3 个月前
此快照最后确认于
2025/12/03 03:50
3 个月前
查看原文

多源最短路

Floyd:

时间复杂度：

O(N3)O(N^3)

实现方式：

三重循环枚举起点，终点，中转点，然后进行松弛操作

代码模版：

CPP
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		}
	}
	return;
}
其中，k是中转点
注意：中转点k的枚举必须写在最外层！

优点：

  1. 代码量小，好记，考试时遇到单源最短路的题目可以用Floyd骗一点分。

缺点：

  1. 时间复杂度高，大概n到10310^3就会超时。

使用场景：

处理多源最短路且n较小的时候用

单源最短路

Dijkstra:

时间复杂度：

普通版：O(N2)O(N^2)
堆优化版：O(N∗log(M))O(N*log(M))

实现方式：

每一次操作将当前长度最短的路径更新一个点，路径上的点数增加，路径长减少，由短的路->长的路

代码模版：

普通版：
CPP
int dis[500005],n,m,s;
bool vis[500005];
struct node{
	int v,w;
};
vector<node>e[500005];
void dijkstra(){
	for(int i=1;i<=n;i++)dis[i]=1e18;
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int minn=1e18,p;
		for(int j=1;j<=n;j++){
			if(vis[j]==0&&dis[j]<minn){
				minn=dis[j];
				p=j;
			}
		}
		vis[p]=1;
		for(int j=0;j<e[p].size();j++){
			int v=e[p][j].v,w=e[p][j].w;
			if(dis[v]>dis[p]+w)dis[v]=dis[p]+w;
		}
	}
}
堆优化版：
CPP
int n,m,s,dis[100005];
bool vis[100005];
struct node{
	int v,w;
	bool operator < (const node &b) const 
	{
		return b.w<w;
	}
};
vector<node>e[100005];
priority_queue<node>pq;
void dijkstra(){
    pq.push({s,0});
	while(pq.size()){
		node tt=pq.top();
		pq.pop();
		int u=tt.v;
		if(vis[u]==1)continue;
		vis[u]=1;	
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v,w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
                if(!vis[v])pq.push({v,dis[v]});
			}
			
		}
	}
}
一般情况下，我们写代码用的都是堆优化版的dijkstra。

优点：

  1. 速度最快，能解决大多数单源最短路的题目

缺点：

  1. 无法解决负边权问题
  2. 代码较长，容易出错

使用场景：

处理一般单源最短路

Bellman-Ford:

时间复杂度：

O(NM)O(NM)

实现方式：

枚举顶点和每一条边

代码模版：

CPP
int n,k,dis[100005];
struct node{
	int u,v,w;
}e[100005];
void bellman_ford(){
	for(int i=1;i<=n;i++)dis[i]=1e18;
	dis[1]=0;
	while(1){
		bool flag=0;
		for(int i=1;i<=n;i++){
			int u=e[i].u,v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				flag=1;
				dis[v]=dis[u]+w;
			}
		}
		if(!flag)break;
	}
}

优点：

  1. 好写
  2. 可以处理负环问题

缺点：

  1. 速度较慢

使用场景：

处理负环问题，或数据较小的单源最短路

SPFA:

时间复杂度：

O(NM)O(NM)

实现方式：

跟dijkstra差不多

代码模版：

CPP
const int N=1e5+7;
int n,m,s;
struct node{
	int v,w;
};
vector<node>e[N];
queue<int>p;
int dis[N];
bool vis[N];
void spfa(){
	for(int i=1;i<=n;++i){
		vis[i]=0;
		dis[i]=1e18;
	}
	dis[s]=0;
	p.push(s);
	vis[s]=1;
	while(!p.empty()){
		int u=p.front();
		p.pop();
		vis[u]=0;
		for(int i=0;i<e[u].size();++i){
			int v=e[u][i].v;
			int w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					vis[v]=1;
					p.push(v);
				}
			}
		} 	
	}
	return ;
}

优点：

  1. 随机数据速度快
  2. 可以处理负环问题

缺点：

  1. 非随机数据的题目，SPFA容易被卡死

使用场景：

处理负环问题，或随机数据的单源最短路

附：Bellman-Ford和求负环(以P3385 【模板】负环为例)：

Bellman-Ford:

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,dis[100005],t;
struct node{
	int u,v,w;
}e[100005];
bool ballman(){
		for(int i=1;i<=n;i++)dis[i]=1e18;
		dis[1]=0;
	for(int j=1;j<n;j++){
		bool flag=0;
		for(int i=1;i<=m;i++){
			int u=e[i].u,v=e[i].v,w=e[i].w;
			if(dis[u]==1e18)continue;
			if(dis[v]>dis[u]+w){
				flag=1;
				dis[v]=dis[u]+w;
			}
		}
		if(!flag)break;
	}
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(dis[u]==1e18)continue;
		if(dis[v]>dis[u]+w){
			return 1;
		}
	}return 0;
}
signed main(){
	
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		int cnt=0;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			e[++cnt]={u,v,w};
			if(w>=0)e[++cnt]={v,u,w};
			
		}
		m=cnt;
		if(ballman()){
			cout<<"YES\n";
		}else{
			cout<<"NO\n";
		}
	}
		
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...