算法训练（leetcode）第五十二天 | Bellman_ford 队列优化算法（SPFA）、BF算法判断负回路、BF之单源有限最短路(有负回路)

94. 城市间货物运输 I-Bellman_ford 队列优化算法（SPFA）

题目地址

SPFA讲解

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
#include<bits/stdc++.h>
using namespace std;
struct Edge{int to;int val;Edge(int t, int v): to(t), val(v){}
};
int main(){int n,m,left,right,val;cin>>n>>m;vector<list<Edge>> edges(n+1);for(int i=0; i<m; i++){cin>>left>>right>>val;edges[left].push_back(Edge(right, val));}int start = 1;int end = n;vector<int> minDist(n+1, INT_MAX);vector<bool> isInQue(n+1, false);minDist[start] = 0;queue<int> que;que.push(start);while(!que.empty()){int cur = que.front();que.pop();isInQue[cur] = false;for(Edge edge:edges[cur]){int to = edge.to;int val = edge.val;if(minDist[cur]+val<minDist[to]){minDist[to] = minDist[cur]+val;if(!isInQue[to]){que.push(to);isInQue[to] = true;}}}}/*// 对所有边松弛n-1次for(int i=0; i<n; i++){for(vector<int> &edge : edges){int from = edge[0];int to = edge[1];int val = edge[2];// 松弛操作if(minDist[from] != INT_MAX && minDist[to] > minDist[from]+val){minDist[to] =  minDist[from]+val;}}}*/if(minDist[end] == INT_MAX) cout<<"unconnected";else cout<<minDist[end];return 0;
}

95. 城市间货物运输 II-BF算法判断负回路

题目地址

BF算法对图中的边至多松弛n-1次即可得到单源最短路径。若n-1次松弛后再遍历仍有更新操作，则判定为图中出现负回路。

时间复杂度： $O(V\ast E)$
空间复杂度： $O(V)$

// c++
#include<bits/stdc++.h>
using namespace std;int main(){int n,m;cin>>n>>m;vector<vector<int>> edges;vector<int> minDist(n+1, INT_MAX);int left, right, val;for(int i=0; i<m; i++){cin>>left>>right>>val;edges.push_back({left, right, val});}minDist[1] = 0;for(int i=1; i<n; i++){for(vector<int> &edge : edges){int from = edge[0];int to = edge[1];int val = edge[2];if(minDist[from]!=INT_MAX && minDist[from]+val<minDist[to]){minDist[to] = minDist[from] + val;}}}bool flag=false;for(vector<int> &edge : edges){int from = edge[0];int to = edge[1];int val = edge[2];if(minDist[from]!=INT_MAX && minDist[from]+val<minDist[to]){minDist[to] = minDist[from] + val;flag = true;}}if(flag) {std::cout << "circle" << std::endl;}else{if(minDist[n]!=INT_MAX){cout<<minDist[n]<<endl;}else{cout<<"unconnected";}}return 0;
}

96. 城市间货物运输 III-BF之单源有限最短路(有负回路)

题目地址

BF算法对所有边松弛n-1次可以得到源点到与源点n-1条边（n个结点）相连的结点的最短距离。本题要求最多经过k个城市的最短路径，也就是除去起点和终点，中间有k个结点，共k+1个结点，因此有k+1条边，BF算法松弛k+1次。

在有负权值回路的图中，若使用本次松弛结点的最短距离来更新其他结点，会导致陷入在负权值回路中，因此要基于上一次松弛的结果来更新本次结点。

讲解

时间复杂度： $O(V\ast E)$
空间复杂度： $O(V)$

// c++
#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,from,to,val,src,dst,k;cin>>n>>m;vector<vector<int>> edges;for(int i=0; i<m; i++){cin>>from>>to>>val;edges.push_back({from, to, val});}cin>>src>>dst>>k;vector<int> minDist(n+1, INT_MAX);vector<int> minDist_copy(n+1);minDist[src] = 0;for(int i=0; i<=k; i++){minDist_copy = minDist;for(vector<int> &edge : edges){from = edge[0];to = edge[1];val = edge[2];if(minDist_copy[from]!=INT_MAX && minDist_copy[from]+val<minDist[to]){minDist[to] = minDist_copy[from]+val;}}// for (int j = 1; j <= n; j++) cout << minDist[j] << " ";// cout << endl;}if(minDist[dst] != INT_MAX) {cout<<minDist[dst];}else{cout<<"unreachable";}return 0;
}