位址:
判斷負環
描述：
思路：
1、什麼是spfa算法？
stu[N]數組的差別
2、spfa算法步驟
判斷負環解題思路：
代碼：
判斷負環：
位址:
https://www.acwing.com/problem/content/853/
判斷負環
https://www.acwing.com/problem/content/description/854/
描述：
判斷負環：
思路：
1、什麼是spfa算法？
SPFA 算法是 Bellman-Ford算法 的隊列優化算法的别稱，通常用于求含負權邊的單源最短路徑，以及判負權環。SPFA一般情況複雜度是O(m)O(m) 最壞情況下複雜度和樸素 Bellman-Ford 相同，為O(nm)O(nm)。
bellman-ford算法操作如下：
- for n次
- for 所有邊 a,b,w (松弛操作)
- dist[b] = min(dist[b],back[a] + w)
spfa算法對第二行中所有邊進行松弛操作進行了優化，原因是在bellman—ford算法中，即使該點的最短距離尚未更新過，但還是需要用尚未更新過的值去更新其他點，由此可知，該操作是不必要的，我們隻需要找到更新過的值去更新其他點即可。
Bellman_ford算法會周遊所有的邊，但是有很多的邊周遊了其實沒有什麼意義，我們隻用周遊那些到源點距離變小的點所連接配接的邊即可，隻有當一個點的前驅結點更新了，該節點才會得到更新；是以考慮到這一點，我們将建立一個隊列每一次加入距離被更新的結點。
stu[N]數組的差別
1] Dijkstra算法中的st數組儲存的是目前确定了到源點距離最小的點，且一旦确定了最小那麼就不可逆了(不可标記為true後改變為false)；SPFA算法中的st數組僅僅隻是表示的目前發生過更新的點，且spfa中的st數組可逆(可以在标記為true之後又标記為false)。順帶一提的是BFS中的st數組記錄的是目前已經被周遊過的點。
2] Dijkstra算法裡使用的是優先隊列儲存的是目前未确定最小距離的點，目的是快速的取出目前到源點距離最小的點；SPFA算法中使用的是隊列(你也可以使用别的資料結構),目的隻是記錄一下目前發生過更新的點。
例子
2、spfa算法步驟
queue <– 1
while queue 不為空
(1) t <– 隊頭
queue.pop()
(2)用 t 更新所有出邊 t –> b，權值為w
queue <– b (若該點被更新過，則拿該點更新其他點)
判斷負環解題思路：
代碼：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e5+10;
int n,m;
//稀疏表用鄰接表存儲,w[N]存儲的是權重
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
//spfa 的st數組僅僅隻是表示目前點有沒有被更新過，目前點在不在隊列裡
//dijkstra算法的st儲存确定了到源點距離最小的點
bool stu[N];
queue<int>q;
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){
q.push(1);
dist[1]=0;
stu[1]=true;
while(!q.empty()){
auto temp=q.front();
q.pop();
stu[temp]=false;
//i存儲與temp節點相連通的節點的編号,是以w[i]存儲的就是temp節點到j節點邊的權重
for(int i=h[temp];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[temp]+w[i]){
//dist[temp] 存儲從1~temp的距離，w[i]存儲從temp~j的距離
dist[j]=dist[temp]+w[i];
if(!stu[j]){//隻有當目前點不在隊列裡，才會加入隊列
q.push(j);
stu[j]=true;
}
}
}
}
if(dist[n]==0x3f3f3f3f) cout<<"impossible";
else cout<<dist[n];
}
int main(){
cin>>n>>m;
//初始化dist[N]為無窮大
memset(dist,0x3f,sizeof dist);
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
//m條邊,但有重邊，是以當節點間有重邊時，取邊長最小的一條邊
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
spfa();
return 0;
}
判斷負環：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
queue<int>q;
const int N=1e4+10;
int h[N],e[N],ne[N],w[N],idx;
bool stu[N];
//dist存放從1~x号節點的最短距離，cnt[N]存放從1~x号節點中的邊數
int dist[N],cnt[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool spfa(){
dist[1]=0;
//将n個節點全部加入隊列，僅僅把1節點加入的化，它可能不走有負環的路
for(int i=1;i<=n;i++){
q.push(i);
stu[i]=true;
}
while(!q.empty()){
auto temp=q.front();
q.pop();
stu[temp]=false;
for(int i=h[temp];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[temp]+w[i]){
dist[j]=dist[temp]+w[i];
cnt[j]=cnt[temp]+1;
//不一定要cnt[n]>=n隻要有一個節點邊數超過n，就說明有負環
if(cnt[j]>=n) return true;
if(!stu[j]){
stu[j]=true;
q.push(j);
}
}
}
}
return false ;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
if(spfa()) cout<<"Yes";
else cout<<"No";
return 0;
}