文章目录
*关于Bellman ford和SPFA算法的详解
我是白嫖的leetcode会员，然后看了关于图单源最短路径的讲解，讲解的非常好(虽然没代码演示，但基本上一看思路就有了)。
-
为了让大家也白嫖到视频资源，我把视频上传到了YouTube(国内会有版权问题，发不出)
大家有能力上油管的建议去看看，否则这代码肯定是看不懂的。。。 -
视频链接：
适用性分析(先看视频)
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 = read();
m = read();
//记录m条边的关系
pos MAP[m];
for(int i=0;i<m;i++){
int a =read(),c = read(),len = read();
MAP[i] = {a,c,len};
}
dp[1] = 0;
//外面一层代表遍历边的次数，最多为n-1次
for(int i=1;i<=n-1;i++){
bool flag = true;
for(int k=0;k<m;k++){
if(dp[MAP[k].j]>dp[MAP[k].i]+MAP[k].len){
dp[MAP[k].j] = dp[MAP[k].i]+MAP[k].len;
flag = false;
}
}
//一旦有一轮遍历未更新一次，则弹出循环，得出答案
if(flag)
break;
}
for(int i=2;i<=n;i++){
cout<<dp[i]<<endl;
}
}
最终优化–SPFA算法
毕竟SPFA的全称为Shortest Path Faster Algorithm，也得当担得起这个名字啊🤣
主要因为用STL容器存储数据的原因，所以似乎稍慢。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int n,m;
//以边为单位遍历更新,再进一步优化便得到得到SPFA算法
//我们需要构造一个以任一点为起点的，它所连接的通路的结构，以方便队列进行操作，用哈希表进行映射最好
map<int,vector<pair<int,int> > >MAP;
vector<int>dp(20001,INT_MAX/2);
queue<int>Q;
//标记结点是否在队列之中
bool check[20001] = {false};
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].push_back(make_pair(c,len));
}
dp[1] = 0;
Q.push(1);
check[1] = true;
while(!Q.empty()){
int node = Q.front();Q.pop();check[node] = false;
vector<pair<int,int> >& t = MAP[node];
//以node为起点开始更新，一旦被更新且队中无该结点，则入队。
for(int i=0;i<t.size();i++) {
if(dp[t[i].first]>dp[node]+t[i].second){
dp[t[i].first] = dp[node]+t[i].second;
//入队操作
if(!check[t[i].first])
Q.push(t[i].first);
check[t[i].first] = true;
}
}
}
for(int i=2;i<=n;i++){
cout<<dp[i]<<endl;
}
}