最短路径算法总结（Dijkstra、Bellman-ford、SPFA和Floyd）

本文主要是介绍最短路径算法总结（Dijkstra、Bellman-ford、SPFA和Floyd），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在最短路径算法中，常用的有Dijkstra、Bellman-ford、spfa、Floyd这四大算法

Dijkstra：迪克斯特拉算法
Bellman-ford：贝尔曼-福特算法
SPFA：Shortest Path Faster Algorithm算法
Floyd：弗洛伊德算法

四大算法介绍

简介

Dijkstra：是一种用于求解单源最短路径的贪心算法。它从起始节点开始，逐步扩展到其他节点，每次选择当前距离起始节点最近的节点进行扩展。通过不断更新节点的最短距离，最终得到起始节点到其他所有节点的最短路径

Belman-ford：是一种用于求解单源最短路径的动态规划算法。它通过对图中所有边进行松弛操作，逐步更新节点的最短距离。贝尔曼-福特算法可以处理带有负权边的图，并且能够检测出图中是否存在负权回路

SPFA：是一种用于解决单源最短路径问题的算法，它也是对Bellman-Ford算法的一种优化。SPFA算法的基本思想是利用队列来存储待处理的顶点，通过不断地松弛操作来更新顶点的最短路径值

Floyd：又称插点法，是一种用于求解任意两点间最短路径的动态规划算法。它通过不断更新节点之间的最短距离，逐步求解出所有节点之间的最短路径。弗洛伊德算法适用于有向图或无向图，可以处理带有负权边的图

时间复杂度

算法	时间复杂度
一般Dijkstra	O(n^2)
堆优化版Dijkstra	O(mlogn)
Belman-ford	O(nm)
spfa	一般O(m),最坏O(nm)
Floyd	O(n^3)

适用场景

算法	适用场景	最短路问题
一般Dijkstra	所有边权都是正数	单源最短路
堆优化版Dijkstra	所有边权都是正数
Belman-ford	存在负权边且限制经过边数
spfa	存在负权边
Floyd	不能有负权回路	多源汇最短路

四大算法思路

1.1、一般Dijkstra

初始条件：

节点1到其余节点的初始距离为正无穷大
节点1到节点1距离为0

最外层循环（n）：

从未标记的节点中选择距离出发点最近的节点并标记该点
计算刚标记点的所有出边，若(节点1到该点距离+出边权重) < 已存的出边目标节点的距离，就更新节点距离

代码模版：

const int N = 10010;//根据题目具体定义数字大小
typedef int INF = 0x3f3f3f3f;//表示正无穷大int dist[N];//表示节点1到节点n的距离解集
bool st[N];//表示节点n是否被标记
int g[N][N];//表示边//初始化
int dist[1]=0,dist[2]=INF,......,dist[n]=INF;int Dijkstra(){//初始条件memset(dist, 0x3f, sizeof dist);dist[1] = 0;  //遍历n次循环，即标记n个点并扩展了n个点的所有出边for(int i=1 ; i <= n ; i++){1、从未标记的节点中选择距离出发点最近的节点并标记该点int t = -1;for（int j=1 ; j <=n ; j++）{if(!st[i] && (t==-1 || dist[t]>dist[j]){t = j;}}st[t] = true;2、计算刚标记点的所有出边for(int j=1;j <= n ; j++){dist[j] = min(dist[j],dist[t]+g[t][j]);}}if (dist[n] == 0x3f3f3f3f) {return -1;}return dist[n];}

总结：一般Dijkstra算法，在第二层循环中有冗余，即 j 有多次非必要遍历。当n在100000时，时间复杂度为n^2的话可能会导致超时，因此当图为稀疏图时，可以采用堆优化版的Dijkstra算法

1.2、堆优化版Dijkstra

初始条件：

节点1到其余节点的初始距离为正无穷大
节点1到节点1距离为0

循环：

从队列中未标记的节点取出距离出发点最近的节点并标记该点
计算刚标记点的所有出边，若更新了节点距离，并将后续节点压入队列

代码模版：

//定义pair类型，其值分别代表节点1到该节点距离，节点号
typedef pair<int,int> PII;
const int N=1e6+10;
int dist[N];//解集
bool st[N];//表示该节点是否被标记//使用邻接表来存储边
int h[N],e[N],ne[N],w[N],idx=0;
//e[]存储目标节点,w[]存储权重，h[]的索引代表起始节点int Dijkstra(){//初始条件memset(dist,0x3f,sizeof(dist));dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1});//压入初始状态    //循环while(heap.size){//标记节点auto t = heap.top;heap.pop();int ver=t.second,distance=t.first;if(st[ver]){continue;}st[ver] = true;//扩展节点for(int i=h[ver] ; i != -1 ; i = ne[i]){int j = e[i]if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];heap.push({dist[j],j});}}}    if(dist[n] == 0x3f3f3f3f){return -1;}return dist[n];}

思考：优先队列heap采用的是greater小顶堆，所以距离最小的会放在第一位，因此取出队头时就保证了取出的点是队列中距离最小的。Bellman-ford和SPFA算法一样可以用于判断负环是否存在。

2、Bellman-ford

初始条件：

节点1到其余节点的初始距离为正无穷大
节点1到节点1距离为0

最外层循环（n）：

遍历所有边并进行松弛操作

代码模版：

const int N=510,M=10010;//点数和边数，根据题目自由设置
//边的结构体
struct Edge{int a,b,w;
}Edges[M];
//dist[]解集，backup[]下次循环前解集结果
int dist[N],backup[N];//n：输入的点数
//m：输入的边数
//k：输入的只能经过几条边
int n,m,k;void Bellman-ford(){//初始条件memset(dist,0x3f,sizeof(dist));dist[1]=0;for(int i=1 ; i <= k ; i++){//备份memcpy(backup,dist,sizeof(dist));//遍历所有边并进行松弛操作for(int j=0 ; j < m ; j++){auto e = Edges[j];dist[e.b] = min(dist[e.b],backup[e.a]+e.w);}}}

总结：

1、因为SPFA算法的效率高于Bellman-ford算法，因此Bellman-ford算法一般用于有边数限制并存在负权的情况。

2、最外层的n次循环有一个实际意义为从节点1到节点x经过的边不超过n条边。

3、bankup的意义为防止串联，串联即在循环中dist经过一次循环并不止更新一条边，而是更新点以及它的所有出边。串联会导致调用错误的数据，导致结果不正确，

3、SPFA

3.1求最短路

初始条件：

节点1到其余节点的初始距离为正无穷大
节点1到节点1距离为0

循环：

从队列取出的队头并取消标记
对该节点进行出边循环（松弛操作）

求最短路代码模版：

const int N=1e5+10;
int dist[N];//解集
bool st[N];//表示该节点是否在队列中//使用邻接表来存储边
int h[N],e[N],ne[N],w[N],idx=0;
//e[]存储目标节点,w[]存储权重，h[]的索引代表起始节点int spfa(){//初始条件memset(dist,0x3f,sizeof(dist));dist[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(dist[j] > dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){//如果目标不在队列则加入q.push(j);st[j]=true;}}}}return dist[n];
}

3.2判断负环

初始条件：

所有点都压入队列中

循环：

从队列取出的队头并取消标记
对该节点进行出边循环（松弛操作）

判断负环代码模版：

const int N = 2010, M = 10010;int dist[N];//解集
int cnt[N];//边数
bool st[N];//该节点是否在队列中//使用邻接表来存储边
int h[N],e[N],ne[N],w[N],idx=0;
//e[]存储目标节点,w[]存储权重，h[]的索引代表起始节点bool spfa(){//将所有节点都压入队列（负环不确定在哪个位置）queue<int> q;for (int i = 1; i <=n ; ++i) {st[i] = true;q.push(i);}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 (dist[j] > dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j] = cnt[t] + 1;//如果边数大于n，说明有n+1个点，但只有n个点，此时确定有负环返回true；if (cnt[j] >= n){return true;}if(!st[j]){q.push(j);st[j]=true;}}}}return false;
}

4、Fyold

初始条件：

所有节点到它本身的距离为0
所有节点到其他节点为无穷大

循环：

三层循环，从外到内分别是k，i，j。k代表迭代次数。

const int N=210,INF=1e9;
int n,m,Q;//输入的点数、边数、求解数
//dist[][]一开始作为边矩阵的输入，在调用Floyd后dist[x][y]为x到y的最短距离
int dist[N][N];void Floyd(){//初始条件for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if(i == j){//防止自环dist[i][j] = 0;}else{//其余节点为真无穷大dist[i][j] = INF;}}}for (int k = 1; k <= n; ++k) {for(int i = 1; i <= n; i++){for(int j = 1; j <= n;j++){dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}
}