图的最短路径算法对比
图的最短路径算法对比
| Floyd | Dijkstra | Bellman-Ford | 队列优化的Bellman-Ford | |
|---|---|---|---|---|
| 空间复杂度 | O(N^2) | O(M) | O(M) | O(M) |
| 时间复杂度 | O(N^3) | O((M+N)logN) | O(NM) | 最坏情况下也是O（NM） |
| 适用情况 | 稠密图 | 稠密图 | 稀疏图 | 稀疏图 |
| 负权 | 可以解决 | 不能解决 | 可以解决 | 可以解决 |
| 有负权边 | 可以处理 | 不能处理 | 可以处理 | 可以处理 |
| 判断是否有负权回路 | 不能 | 不能 | 可以判定 | 可以判定 |
Floyd算法整体时间复杂度高，但可以处理带有负权边的图（无法处理负权回路），编码复杂度小
Dijkstra算法无法处理带有负权边以及负权回路的图，但具有可扩展性
Bellman-Ford算法可以处理带有负权边和负权回路的图
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 星辰微光的博客！
相关推荐
2021-11-09
C++学习记录算法篇-埃氏筛质数
C++学习记录算法篇 埃氏筛质数 埃氏筛质数法原理：质数的倍数都不是质数，因此将质数的倍数都筛除，剩下的都是质数。 示例： 假设要筛选从1到a(a>=2)内的所有质数： 1.先设所有数均为质数(利用布尔) 2.将1设为不是质数 3.从2开始，2的倍数均不是质数；再从3开始，3的倍数均不是质数 4.此时遇到4，4在筛除2的倍数时已经被筛除，则跳过4，从5开始，以此类推筛除所有非质数 5.3，4流程重复至根号内a即可 代码示例： 123456789101112131415161718192021//以a=100为例bool is_prime[101];for(int i=1;i<=100;i++){ is_prime[i]=true;}//先假设所有的数都是质数is_prime[1]=false;//1不是质数//开始筛选for(int i=2;i<=pow(100,0.5);i++){ if(is_prime[i]==true) { for(int j=2;j*i<=100;j++) ...
2022-02-27
C++学习记录算法篇-快读与快写
C++学习记录算法篇-快读与快写 快读 1234567int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f;} 快写 12345void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0');}
2022-05-02
C++学习记录算法篇—归并排序
C++学习记录算法篇—归并排序 一、归并排序： 归并排序利用了分治思想，即把大问题先拆分为小问题，对小问题进行求解，最后合并成大问题的解。在归并排序中体现为：先把数组拆分为许多小数组，对小数组进行排序，再把有序的小数组合并成有序的大数组。 二、归并排序的实现： 首先是归并排序的入口，在这个入口创建临时数组，并进行划分，最后在排序完成后删除临时数组 12345678910void merge_sort(int arr[],int n){ //首先分配辅助数组 int* tempArr = new int[n]; //分配完，进行数组的划分 msort(arr, tempArr, 0, n - 1); //排序完后，删除临时数组 delete tempArr; return;} 接下来是数组的划分，传入的参数为： 欲划分的数组 临时数组 划分的起点（最开始是0） 划分的终点（最开始是n-1） 首先一直划分数组，直到每个小数组只有一个元素，这是一个递归的过程 划分数组后，进入合并阶段 123456789101112131415void...
2022-05-02
C++学习记录算法篇-堆排序
C++学习记录算法篇-堆排序 一、堆 堆是一颗完全二叉树 如果堆的每一个节点（叶子节点除外）都大于他的子节点，这样的堆称为大根堆 如果堆的每一个节点（叶子节点除外）都小于他的子节点，这样的堆称为小根堆 对于用数组储存的堆，有以下运算性质： 某个节点i的父节点下标为：（i-1）/2 （整数除法） 某个节点i的左孩子节点下标为： i*2+1 某个节点i的右孩子节点下标为： i*2+2 二、堆排序（以从小到大为例） 利用堆的性质进行排序：从小到大使用大根堆，从大到小使用小根堆 大根堆的根节点的值最大，因此不断地把根节点放到数组的最末端，放完再维护堆，就可以实现从小到大排序 三、代码实现： 首先实现堆的维护： 对于某个待维护的下标，我们要维护其子节点，子节点的子节点…直到叶子节点，这是一个递归的过程 12345678910111213141516171819202122//维护堆的性质，以大根堆为例：//所需要的参数：数组，数组的长度，待维护的下标void heapify(int arr[], int n, int...
2022-05-02
C++学习记录算法篇—快速排序
C++学习记录算法篇—快速排序 一、快速排序的过程（从小到大排为例）： 首先，假设基准数为最左边的数。 然后，让两个“哨兵”从最左边和最右边向中间探测，从左边出发的哨兵找比基准数大的数，从右边出发的哨兵找比基准数小的数 注意，因为是从小到大排，所以右边的哨兵要先出发 两个哨兵都“停下”（即找到了符合要求的数），交换两个“哨兵”的值，接着继续探测，继续交换，直到两个哨兵相遇为止 两个哨兵相遇后，交换基准数与相遇时所指示的数。 此时，基准数左边都小于基准数，基准数右边都大于基准数，这也是为什么要右边哨兵先动的原因 至此，基准数归位，接着对基准数的两边再次进行快速排序，这是一个递归的过程。 可以看到，快速排序就是不断地把基准数归位的过程 下面是代码： 12345678910111213141516171819202122232425262728293031323334353637//快速排序函数void quicksort(int l, int r)//接受最左边数字的下标left，和最右边数字的下标right{ int i, j, t, temp; if (l >=...
2022-01-25
C++学习记录算法篇：深度优先搜索1-n的全排列
C++学习记录算法篇：深度优先搜索1-n的全排列 深度优先搜索的核心思想是**“不撞南墙不回头”，即对每一个路径进行深入直到不能深入为止**，之后再退回上一步，继续尝试新的路径，直到把每一条路径都尝试一遍。 核心代码如下： 1234567891011121314void dfs(int step){ 判断边界//判断边界，step是否已经到最后一步，是的话返回 //尝试每一种可能 for(int i=1;i<=n;i++) { //尝试 dfs(step+1);//继续下一步,这是一个递归的过程 } return;//返回} 案例：求n的全排列： 这里通过将手上标有1~n的牌放到n个箱子里，来模拟全排列的过程，代码如下： 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using...
