本文主要是介绍最短路常用算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

弗洛伊德(Floyd-Warshall)

时间复杂度\(O(n^3)\)
多元最短路，核心思想是依次将所有点作为中转点并更新所有路径。
核心代码也只有5行

for(int i=1;i<=n;++i)//外层循环一定是中转点
  for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
      if(g[j][k]>g[j][i]+g[i][k])
          g[j][k]=g[j][i]+g[i][k];

迪杰斯特拉(dijkstra)

单源最短路，基于贪心的思想求得每个点到原点的最短距离。
注意路径不能为负。
每次选择一个离原点最近的点，那么这个点离原点的最短距离也就确定了，然后更新所有与这个点相邻点的距离。
例题：P3371 【模板】单源最短路径（弱化版）
参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=1e4+10;
const int M=5e5+10;
int dis[N];
struct {
	int to,next,w; 
}e[M];
int head[N],cnt;
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
struct node{
	int d,id;
	const bool operator<(const node a)const{
		return d>a.d;
	}
	node(){}
	node(int a,int b):d(a),id(b){}
};
bool vis[N];
void djk(int s){
	dis[s]=0;
	for(int i=1;i<=n;++i){
		int ind,Min=1e9;
		for(int j=1;j<=n;++j){//找到离原点最近的点
			if(!vis[j]&&dis[j]<Min){
				ind=j;
				Min=dis[j];
			}
		}
		vis[ind]=1;
		for(int j=head[ind];j;j=e[j].next){//更新
			int to=e[j].to;
			dis[to]=min(dis[to],dis[ind]+e[j].w);
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i)dis[i]=INT_MAX;
	int u,v,w;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	djk(s);
	for(int i=1;i<=n;++i)printf("%d ",dis[i]);
	return 0;
}

该算法是djk朴素算法，时间复杂度为\(O(n^2)\)
djk堆优化(劣化)
如果使用堆来解决找离原点最近的点，那么这部分的时间复杂度变为\(O(logN)\)，总的时间复杂度是\(O((M+N)logN)\)
最坏情况下\(M=N^2\)，堆优化就变成了队劣化。
参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=1e4+10;
const int M=5e5+10;
int dis[N];
struct {
	int to,next,w; 
}e[M];
int head[N],cnt;
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
struct node{
	int d,id;
	const bool operator<(const node a)const{
		return d>a.d;
	}
	node(){}
	node(int a,int b):d(a),id(b){}
};
priority_queue<node>q;
bool vis[N];
void djk(int s){
	dis[s]=0;
	q.push(node(0,s));
	node now;
	while(q.size()){
		now=q.top();//这里的复杂度为NlogN
		q.pop();
		int id=now.id,to;
		if(vis[id])continue;//找到最短路的点直接跳过
		vis[id]=1;
		for(int i=head[id];i;i=e[i].next){
			to=e[i].to;
			if(dis[to]>dis[id]+e[i].w){//这里的复杂度为MlogN
				dis[to]=dis[id]+e[i].w;
				q.push(node(dis[to],to));
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i)dis[i]=INT_MAX;
	int u,v,w;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	djk(s);
	for(int i=1;i<=n;++i)printf("%d ",dis[i]);
	return 0;
}

贝尔曼-福特(Bellman-Ford)

单源最短路，这种算法可以解决带负权边的图(也可以判断图中是否有负环)。
基本思路与弗洛伊德有点像，不断地向图中加入中转边。
看一张图

只看其中的一条路径

如果加边的方向刚好是从左到右，那么很快就能得到1->6的最短路，
如果方向相反，把所有边加入依次只能得到1->2的最短路。
为了解决加边随机性的问题，我们需要重复加边。
核心代码

for(int k=1;k<=n-1;++k)
  for(int i=1;i<=m;++i)//一次加入(松弛)所有边，由于顺序可能不是最优的，所以这个过程要重复n-1次
    if(dis[v[i]]>dis[u[i]]+w[i])
      dis[v[i]]=dis[u[i]]+w[i];

检查负权回路只需多松弛一次，若还能更新最短路，则由负权回路
时间复杂度\(O(MN)\)

Bellman-Ford的队列优化

在每一次松弛后，有一些点已经求得了最短距离，它们不再受接下来松弛的影响。
这就启发我们只对最短距离发生变化的点的出边进行松弛。
整个过程用队列来维护即可。
例题：P3371 【模板】单源最短路径（弱化版）
参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=1e4+10;
const int M=5e5+10;
int dis[N];
struct {
	int to,next,w; 
}e[M];
int head[N],cnt;
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
struct node{
	int d,id;
	const bool operator<(const node a)const{
		return d>a.d;
	}
	node(){}
	node(int a,int b):d(a),id(b){}
};
queue<node>q;
bool vis[N];
void spfa(int s){
	dis[s]=0;
	q.push(node(0,s));
	node now;
	while(q.size()){
		now=q.front();
		q.pop();
		int id=now.id,to;
		vis[id]=0;
		for(int i=head[id];i;i=e[i].next){
			to=e[i].to;
			if(dis[to]>dis[id]+e[i].w){
				dis[to]=dis[id]+e[i].w;
				if(!vis[to])q.push(node(dis[to],to)),vis[to]=1;//一个点重复入队没有意义
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i)dis[i]=INT_MAX;
	int u,v,w;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa(s);
	for(int i=1;i<=n;++i)printf("%d ",dis[i]);
	return 0;
}

然而它最坏复杂度也为\(O(MN)\)
如果一个点入队超过n次，那么存在负环。

总结

这篇关于最短路常用算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！