Bellman_ford 队列优化算法（又名SPFA）
文章讲解：代码随想录
为啥要优化？
因为在松弛的过程中 做了很多无用功
所以用队列来记录需要松弛的边
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <list>
struct Edge{
int s,t;
int val;
Edge(int _s,int _t,int _val):s(_s),t(_t),val(_val){}
};
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<list<Edge>>grid(n+1);
vector<bool>isInQueue(n+1,false);
vector<int>minDist(n+1,INT_MAX);
queue<int>myQueue;
while(m--){
int s,t,v;
cin>>s>>t>>v;
grid[s].push_back(Edge(s,t,v));
}
int start=1;
int end=n;
minDist[start]=0;
myQueue.push(start);
while(!myQueue.empty()){
int cur=myQueue.front();
myQueue.pop();
isInQueue[cur]=false;//出队后需标记
const auto& edges=grid[cur];
for(auto& edge:edges){
int s=edge.s;
int t=edge.t;
int val=edge.val;
if(minDist[s]==INT_MAX)continue;
minDist[t]=min(minDist[s]+val,minDist[t]);
if(!isInQueue[t]){
myQueue.push(t);
isInQueue[t]=true;//入队后需标记
}
}
}
if(minDist[end]!=INT_MAX)cout<<minDist[end];
else cout<<"unconnected";
}bellman_ford之判断负权回路
题目链接：95. 城市间货物运输 II
文章讲解：代码随想录
思路：
普通版的福特算法，考虑第n次松弛是否会出现更短的路径。出现就标记
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
//数据读取
int n,m;
cin>>n>>m;
vector<vector<int>>grid;
vector<int>minDist(n+1,INT_MAX);
while(m--){
int s,t,v;
cin>>s>>t>>v;
grid.push_back({s,t,v});
}
int start=1;
int end=n;
minDist[start]=0;
bool flag=false;
for(int i=1;i<=n;i++){
for(int j=0;j<grid.size();j++){
int s=grid[j][0];
int t=grid[j][1];
int val=grid[j][2];
if(minDist[s]==INT_MAX)continue;
if(i<n){
minDist[t]=min(minDist[t],minDist[s]+val);
}else{
if(minDist[s]+val<minDist[t]) flag=true;
}
}
}
//输出
if(flag){cout<<"circle";return 0;}
if(minDist[end]!=INT_MAX)cout<<minDist[end];
else cout<<"unconnected";
}队列优化版的福特算法 ，统计节点入队次数。如果节点入队次数超过n，说明出现环。
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <list>
struct Edge{
int s,t;
int val;
Edge(int _s,int _t,int _val):s(_s),t(_t),val(_val){}
};
using namespace std;
int main(){
//数据读取
int n,m;
cin>>n>>m;
vector<list<Edge>>grid(n+1);
vector<bool>isInQueue(n+1,false);
vector<int>minDist(n+1,INT_MAX);
queue<int>myQueue;
while(m--){
int s,t,v;
cin>>s>>t>>v;
grid[s].push_back(Edge(s,t,v));
}
int start=1;
int end=n;
minDist[start]=0;
myQueue.push(start);
bool flag=false;
vector<int>count(n+1,0);//统计每个节点的入队数量
while(!myQueue.empty()){
int cur=myQueue.front();
myQueue.pop();
isInQueue[cur]=false;//出队后需标记
const auto& edges=grid[cur];
for(auto& edge:edges){
int s=edge.s;
int t=edge.t;
int val=edge.val;
if(minDist[s]==INT_MAX)continue;
minDist[t]=min(minDist[s]+val,minDist[t]);
if(!isInQueue[t]){
myQueue.push(t);
isInQueue[t]=true;//入队后需标记
count[t]++;
if(count[t]==n){
flag=true;
while(!myQueue.empty()){myQueue.pop();}//这里是防止再次进入while循环
break;
}
}
}
}
//输出
if(flag){cout<<"circle";return 0;}
if(minDist[end]!=INT_MAX)cout<<minDist[end];
else cout<<"unconnected";
}bellman_ford之单源有限最短路
题目链接：96. 城市间货物运输 III
文章讲解：代码随想录
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>>grid;
while(m--){
int s,t,v;
cin>>s>>t>>v;
grid.push_back({s,t,v});
}
int start,end,k;
cin>>start>>end>>k;
vector<int>minDist(n+1,INT_MAX);
minDist[start]=0;
for(int i=1;i<=k+1;i++){
auto copy_minDist=minDist;
for(int j=0;j<grid.size();j++){
int s=grid[j][0];
int t=grid[j][1];
int val=grid[j][2];
if(copy_minDist[s]==INT_MAX)continue;
minDist[t]=min(copy_minDist[s]+val,minDist[t]);
}
}
if(minDist[end]==INT_MAX)cout<<"unreachable";
else cout<<minDist[end];
}本题的关键是对松弛的次数有严格要求，不能多松弛。
关键点1：
松弛此时为k+1，
关键点2：
每轮松弛都要基于上一轮的minDist数组，所以要复制一份