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

2024-02-25 23:36
文章标签 算法 总结 路径 最短 spfa dijkstra floyd bellman ford

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

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

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

四大算法介绍

简介

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

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

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

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

时间复杂度

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

适用场景

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

四大算法思路

1.1、一般Dijkstra

初始条件：

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

最外层循环（n）：

  1. 从未标记的节点中选择距离出发点最近的节点并标记该点
  2. 计算刚标记点的所有出边，若(节点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到其余节点的初始距离为正无穷大
  2. 节点1到节点1距离为0

循环：

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

代码模版：

//定义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到其余节点的初始距离为正无穷大
  2. 节点1到节点1距离为0

最外层循环（n）：

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

代码模版：

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到其余节点的初始距离为正无穷大
  2. 节点1到节点1距离为0

循环：

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

求最短路代码模版：

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判断负环

初始条件：

  1. 所有点都压入队列中

循环：

  1. 从队列取出的队头并取消标记
  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

初始条件：

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

循环：

  • 三层循环，从外到内分别是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]);}}}
}

总结：三个循环嵌套，i，j的循环是任意两个点，而 k 则是两个点之间所经过的第三个点，我们就是在循环之中不断比较从i到j的距离与从 i 到 k 距离加上从 k 到 j 距离的大小，如果经过这个点，路径变短了，我们就接受这个点，认为可以经过这个点；否则就不经过这个点，就是从 i 到 j 最短

这篇关于最短路径算法总结（Dijkstra、Bellman-ford、SPFA和Floyd）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/747041。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2