求最短路模板详解（floyed()算法、dijkstra()算法、spfa()算法、bellman-ford()算法）

大家好，欢迎来到IT知识分享网。

框架

一、floyed() 算法    

1.限制条件

时间复杂度  o(n^3)  边权为正数

2.常见问题描述

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。

（ps:重边直接保留最小的边，自环直接删掉就可以）

再给定 k 个询问，每个询问包含两个整数 x和 y，表示查询从点 x到点y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

3.模板

(1).初始化

for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i==j) d[i][j]=0; else d[i][j]=inf; } } 

(2).看是有向图,还是无向图 

while(m--) { int u,v,w; cin>>u>>v>>w; d[u][v]=min(d[u][v],w);//单向图 d[u][v]=d[v][u]=min(d[u][v],w);//无向图 } 

 (3).核心代码

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

 二、dijkstra()算法

1.限制条件

朴素版时间复杂度 o(n^2)， 堆优化版时间复杂度 o(mlog(n))， 边权为正

2.常见问题描述

(a).给定一个 n个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n 号点，则输出 −1。

(b).求从1号点到剩下(n-1)个点的距离的和以及从(n-1)个点到1号点的最短距离和

可以用dijkstra(1)遍历一遍，求1号点到剩下（n-1）个点的距离；

再用dijkstra(1+n)遍历一遍，求这（n-1）个点到n号点的距离；

3.根据边数和顶点数，判断是用邻接矩阵还是邻接表

稠密图用邻接矩阵，稀疏图邻接表
稠密图指边的条数E接近|V|的平方
稀疏图指边的条数E远小于|V|的平方 

4.模板（朴素版）

(1).初始化

int a[N][N]; bool st[N];//标记i结点的最短路是否确定，确定标记true; int dis[N];//从1结点到i结点的距离 memset(a,0x3f,sizeof(a));

(2).看是有向图,还是无向图

while(m--) { int u,v,w; cin>>u>>v>>w; d[u][v]=min(d[u][v],w);//单向图 d[u][v]=d[v][u]=min(d[u][v],w);//无向图 }

(3).核心代码

int dijkstra() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; int i,j; for(i=0; i<n; i++) { int t=-1; for(j=1; j<=n; j++) { if(!vis[j]&&(t==-1||dis[t]>dis[j])) { t=j; } } vis[t]=true;//将t加到vis中 for(j=1; j<=n; j++)//用t更新其他点的距离 { dis[j]=min(dis[j],dis[t]+a[t][j]); } } //memset是按字节进行初始化的，int包含四个字节 //初始化之后就是0x3f3f3f3f; if(dis[n]>=0x3f3f3f3f) return -1; else return dis[n]; }

5.模板 （堆优化版）

(1).初始化

typedef pair<int,int>PII; const int N=110,M=N*2; const int inf=0x3f3f3f3f; int n,m; int h[N],ne[M],w[M],e[M]; bool st[M]; int dis[M]; int idx=0; memset(h,-1,sizeof(h));

(2).加边

void add(int x,int y,int z) { w[idx]=z; e[idx]=y; ne[idx]=h[x]; h[x]=idx++; } while(m--) { int x,y,z; cin>>x>>y>>z; add(x,y,z); }

(3).核心代码

int dijkstra() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; priority_queue<PII,vector<PII>,greater<PII> >q; q.push({0,1});//先排距离，再排变量 int i,j; while(q.size()) { PII k=q.top(); q.pop(); int t=k.second,s=k.first; if(st[t]) continue; st[t]=true; for(i=h[t];i!=-1;i=ne[i]) { j=e[i]; if(dis[j]>s+w[i]) { dis[j]=s+w[i]; q.push({dis[j],j}); } } } if(dis[n]>=0x3f3f3f3f/2) return -1; else return dis[n]; }

6.相关例题

P1629 邮递员送信 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

有一个邮递员要送东西，邮局在节点 1。他总共要送 n−1 样东西，其目的地分别是节点 2到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。

Input

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。

第二行到第 (m+1) 行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。

Output

输出仅一行，包含一个整数，为最少需要的时间。

Sample 1

5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2

83

Hint

对于 30%30% 的数据，1≤n≤200。

对于 100%100% 的数据，1≤n≤103，11≤m≤105，1≤u,v≤n，1≤w≤104，输入保证任意两点都能互相到达。

1.思路

可以用dijkstra(1)遍历一遍，求1号点到剩下（n-1）个点的距离；

再用dijkstra(1+n)遍历一遍，求这（n-1）个点到n号点的距离；

2代码 

#include<bits/stdc++.h> #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N=2e3+10; const int inf=0x3f3f3f3f; int n,m; int dis[N]; bool st[N]; int a[N][N]; void dijkstra(int x) { int i,j; memset(dis,0x3f,sizeof(dis)); memset(st,false,sizeof(st)); dis[x]=false; for(i=0;i<n*2;i++) { int t=-1; for(j=1;j<=n*2;j++) { if(!st[j]&&(t==-1||dis[t]>dis[j])) { t=j; } } st[t]=true; for(j=1;j<=n*2;j++) { dis[j]=min(dis[j],dis[t]+a[t][j]); } } } void solve() { cin>>n>>m; int i,j; memset(a,0x3f,sizeof(a)); while(m--) { int u,v,w; cin>>u>>v>>w; a[u][v]=min(a[u][v],w);//求1~(n-1)个点的距离 a[v+n][u+n]=min(a[v+n][u+n],w);//求剩下(n-1)个点到1+n的距离 } int ans=0; dijkstra(1); for(i=2;i<=n;i++) { ans+=dis[i]; } dijkstra(1+n); for(i=2+n;i<=n*2;i++) ans+=dis[i]; cout<<ans<<endl; } signed main() { int t=1; while(t--) { solve(); } return 0; } 

三、bellman-ford（）算法

1.限制条件

bellman()算法时间复杂度o(n*m), 边权可以为负，可以有边数限制

2.常见问题描述

给定一个 n个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n号点的最多经过 k条边的最短距离，如果无法从 1号点走到 n号点，输出 impossible。

注意：图中可能 存在负权回路 。

3.模板

//Bellman-ford 算法o（n*m） #include<bits/stdc++.h> #define endl '\n' //#define int long long #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N=510,M=10010; //const int inf=0x3f3f3f3f; int n,m,k; int dis[N],bp[N]; struct node { int a,b,w; }edge[M]; void bellman_ford() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; int i,j; for(i=0;i<k;i++)//若发生串联，边数限制不起作用 { memcpy(bp,dis,sizeof(dis));//先备份一下,迭代上一次保留的结果 for(j=0;j<m;j++) { int a=edge[j].a,b=edge[j].b,w=edge[j].w; dis[b]=min(dis[b],bp[a]+w);//用上一次迭代的结果更新当前距离 } } if(dis[n]>0x3f3f3f3f/2)//图中可能存在负权边 cout<<"impossible"<<endl; else cout<<dis[n]<<endl; } void solve() { cin>>n>>m>>k; int i,j; for(i=1;i<=m;i++) { int a,b,w; cin>>a>>b>>w; edge[i]={a,b,w}; } bellman_ford(); } signed main() { int t=1; while(t--) { solve(); } return 0; } 

四、spfa（）算法

 1.限制条件

spfa()算法，一般时间复杂度o(m),最坏o(n*m),可以有负权

2.常见问题描述

1）.求最短路

queue<int>q; q.push(1); while(!q.empty()) { 1. int t=q.front(); q.pop(); 2. 更新t的所有初边 t->j; q.push(j); } 

2）.求最长路  

1.利用spfa,将边权设置为负数，跑最短路*（-1）即为最长路 2.当一个原本正权的边无限大的时候，取为相反数，则得到最小的负权边 当一个原本为负权的边无限小的时候，取为相反数，则得到最大的正权边 3.将其add(x,y,-z)进行操作后，求其图中的最短路， 则原本负权最小的边是不会被取到得的， 因此最后的spfa()*(-1)就得到该图中的最长路；

3）.判断负环

(1)1~j dis[j] 最短距离 cnt[j] 边数 (2)更新： dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; 1~~~~t~j 从1到j的边数+一条边==1~j的边数 (3)判断 if(cnt[j]>=n) 意味着有n+1个点,至少两个点相同， 意味着存在一个环,如果该路程还变小，这个环是负环

 相关例题

P1807 最长路 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（1）.求最长路

设 G 为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 1,n 间的最长路径。

Input

输入的第一行有两个整数，分别代表图的点数 n 和边数 m。

第 2到第(m+1) 行，每行 3个整数 u,v,w，代表存在一条从 u 到 v 边权为 w 的边。

Output

输出一行一个整数，代表 1 到 n 的最长路。

若 1 无法到达 n，请输出 −1。

Sample 1

2 1 1 2 1

1

Hint

【数据规模与约定】

• 对于 20%的数据，n≤100，m≤10^3。
• 对于 40% 的数据   n≤10^3,m≤10^4。
• 对于 100% 的数据，1≤n≤1500，0≤m≤5×10^4，1≤u,v≤n，−10^5≤w≤10^5

代码

//利用spfa ,将边权设置为负数，跑最短路*（-1）即为最长路 #include<bits/stdc++.h> #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef pair<int,int>PII; const int N=5e4+10; const int inf=0x3f3f3f3f; int n,m; int h[N],ne[N],w[N],e[N]; bool st[N]; int dis[N]; int idx=0; void add(int x,int y,int z) { w[idx]=z; e[idx]=y; ne[idx]=h[x]; h[x]=idx++; } int spfa() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; queue<int>q; q.push(1); int i,j; while(!q.empty()) { int t=q.front(); q.pop(); st[t]=0; for(i=h[t];i!=-1;i=ne[i]) { j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } if(dis[n]>=0x3f3f3f3f/2) return 1; else return dis[n]; } void solve() { cin>>n>>m; memset(h,-1,sizeof(h)); while(m--) { int x,y,z; cin>>x>>y>>z; add(x,y,-z); } cout<<-1*spfa()<<endl; } signed main() { int t=1; while(t--) { solve(); } return 0; } 

（2） 求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

输入样例：

3 3 1 2 5 2 3 -3 1 3 4 

输出样例：

2

代码 

#include<bits/stdc++.h> #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N=1e5+10; const int inf=0x3f3f3f3f; int n,m; int e[N],ne[N],h[N],w[N]; int idx=0; int dis[N]; bool st[N]; void add(int x,int y,int z) { w[idx]=z; e[idx]=y; ne[idx]=h[x]; h[x]=idx++; } int spfa() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; queue<int>q; q.push(1); st[1]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false;//点从队列出来 for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j]) //如果j不在队列里面 { q.push(j); st[j]=true; } } } } if(dis[n]>=0x3f3f3f3f) cout<<"impossible"<<endl; else cout<<dis[n]<<endl; } void solve() { int i,j; cin>>n>>m; memset(h,-1,sizeof(h)); while(m--) { int x,y,z; cin>>x>>y>>z; add(x,y,z); } spfa(); } signed main() { int t=1; while(t--) { solve(); } return 0; } 

（3） 判断负环

给定一个 n个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

输入样例：

3 3 1 2 -1 2 3 4 3 1 -4 

输出样例：

Yes

 代码：

#include<bits/stdc++.h> #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N=1e5+10; const int inf=0x3f3f3f3f; int n,m; int e[N],ne[N],h[N],w[N],cnt[N]; int idx=0; int dis[N]; bool st[N]; void add(int x,int y,int z) { w[idx]=z; e[idx]=y; ne[idx]=h[x]; h[x]=idx++; } int spfa() { queue<int>q; for(int i=1;i<=n;i++) { st[i]=true;//把所有点都放在队列里面 q.push(i); } //st[1]=true; 从1这个点开始不一定能找到负环 while(q.size()) { int t=q.front(); q.pop(); st[t]=false;//点从队列出来 for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) //如果j不在队列里面 { q.push(j); st[j]=true; } } } } return false; } void solve() { int i,j; cin>>n>>m; memset(h,-1,sizeof(h)); while(m--) { int x,y,z; cin>>x>>y>>z; add(x,y,z); } int ans=spfa(); if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl; } signed main() { int t=1; while(t--) { solve(); } return 0; }