*关于Bellman ford和SPFA算法的详解 我是白嫖的leetcode会员，然后看了关于图单源最短路径的讲解，讲解的非常好(虽然没代码演示，但基本上一看思路就有了)。 为了让大家也白嫖到视频资源，我把视频上传到了YouTube(国内会有版权问题，发不出) 大家有能力上油管的建议去看看，否则这代码肯定是看不懂的。。。 视频链接： Bellman ford算法详解(两种方式及其优化) 由Bellman ford算法的缺陷引出SPFA算法适用性分析(先看视频) Blellman ford算法DP方法：以 dp[i][j] 表示选择最多 i 条边，从起点到 j 的最短距离。每次的更新依赖于上一行 dp[i-1][j] 的答案，故可滚动数组优化为一维数组。时间复杂度O(N^3)多次遍历边的更新方法：提前记录好哪两个结点有边，每进行一次整个边的遍历，就相当于完成了最多选择一条边到达目的地的最短距离的效果。平均时间复杂度 O(N*V)（V是边的个数，极端情况下会掉到 O(N*N*V)的复杂度，因为最多是可以进行 N-1 次循环的) 很明显无论是哪种方式实现，最终都是依赖选择多少条边的结果，所以该算法适用于指定最多经过k条边的最短路径题目。正好有道例题适合他 K 站中转内最便宜的航班 SPFA算法这个算法只是Bellman ford算法的再优化，使得每次选择的边的关系达到最优，大大减少了边的遍历次数,时间复杂度较为稳定(相对Bellmanford稳定很多)的在 O(N*V)。 这个原本也是基于Bellmanford算法优化的，除了无法表示最多经过k条边，其余效率比之前的算法更快，所以适用于求存在负权值的单源最短路径问题，而无法精确为最多经过了多少条边。以题代讲蓝桥杯--最短路 在这里插入图片描述Bellman ford的动态规划解决(超时,过三个) 在这里插入图片描述#include<bits/stdc++.h> using namespace std; #define LL long long int n,m; vector<int>dp(20001,INT_MAX/2); map<int,map<int,int> > MAP; LL read() { LL res = 0; bool f = 1; char c; //先耗掉一个getchar来进行判断符号 c = getchar(); if(c == '-')f = 0; else res+= (c-'0'); while (isdigit(c = getchar())) { res = (LL)res * 10 + (c-'0'); } if (f) return res; return res*-1; } int main(){ n = read(); m = read(); for(int i=0;i<m;i++){ int a =read(),c = read(),len = read(); MAP[a][c] = len; if(a == 1) dp[c] = len; } dp[1] = 0; vector<int>pre = dp; //外层循环经过最多i条路到达该结点的最短距离，最多经过n-1条 //里面几层都是用于更新没一行的数据 for(int i=2;i<=n-1;i++){ for(int j=2;j<=n;j++){ for(int k = 1;k<=n;k++){ int t = MAP[k][j]; if(t) dp[j] = min(dp[j],pre[k]+t); } } pre = dp; } for(int i=2;i<=n;i++){ cout<<dp[i]<<endl; } } Bellman ford按边遍历解决(速度竟比SPFA快，我惊了) 在这里插入图片描述#include<bits/stdc++.h> using namespace std; #define LL long long int n,m; //以边为单位遍历更新 struct pos{ int i; int j; int len; }; vector<int>dp(20001,INT_MAX/2); LL read() { LL res = 0; bool f = 1; char c; //先耗掉一个getchar来进行判断符号 c = getchar(); if(c == '-')f = 0; else res+= (c-'0'); while (isdigit(c = getchar())) { res = (LL)res * 10 + (c-'0'); } if (f) return res; return res*-1; } int main(){ n = r…