在Bellman-Ford演算法之后，我們總算迎來了spfa演算法，其實就如同堆優化Dijkstra演算法之于樸素版Dijkstra演算法，spfa演算法僅僅是對Bellman-Ford演算法的一種優化，但是在形式上，它看起來特別像堆優化Dijkstra演算法罷了！
Bellman—Ford演算法會遍歷所有邊并進行松弛操作，然而我們應該知道很多的更新是無用的，所以我們的優化就體現在這里，因為只有那些前一步被更新的點，它所連接的點才有被更新的意義，所以我們會將被更新的點放入一個佇列中；
注意點：
1) st陣列的作用：判斷當前的點是否已經加入到佇列當中了；已經加入佇列的結點就不需要反復的把該點加入到佇列中了，就算此次還是會更新到源點的距離，那只用更新一下數值而不用加入到佇列當中，
即便不使用st陣列最終也沒有什么關系，但是使用的好處在于可以提升效率，
2) SPFA演算法看上去和Dijstra演算法長得有一些像但是其中的意義還是相差甚遠的:
1] Dijkstra演算法中的st陣列保存的是當前確定了到源點距離最小的點，且一旦確定了最小那么就不可逆了(不可標記為true后改變為false)；SPFA演算法中的st陣列僅僅只是表示的當前發生過更新的點，且spfa中的st陣列可逆(可以在標記為true之后又標記為false)，順帶一提的是BFS中的st陣列記錄的是當前已經被遍歷過的點，
2] Dijkstra演算法里使用的是優先佇列保存的是當前未確定最小距離的點，目的是快速的取出當前到源點距離最小的點；SPFA演算法中使用的是佇列(你也可以使用別的資料結構),目的只是記錄一下當前發生過更新的點，
3) ??Bellman_ford演算法里最后return-1的判斷條件寫的是dist[n]>0x3f3f3f3f/2;而spfa演算法寫的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford演算法會遍歷所有的邊，因此不管是不是和源點連通的邊它都會得到更新；但是SPFA演算法不一樣，它相當于采用了BFS，因此遍歷到的結點都是與源點連通的，因此如果你要求的n和源點不連通，它不會得到更新，還是保持的0x3f3f3f3f，
4) ?? Bellman_ford演算法可以存在負權回路，是因為其回圈的次數是有限制的因此最終不會發生死回圈；但是SPFA演算法不可以，由于用了佇列來存盤，只要發生了更新就會不斷的入隊，因此假如有負權回路請你不要用SPFA否則會死回圈（然而我們可以用spfa來判斷是否存在負權回路），
5) ??由于SPFA演算法是由Bellman_ford演算法優化而來，在最壞的情況下時間復雜度和它一樣即時間復雜度為 O(nm) ，假如題目時間允許可以直接用SPFA演算法去解Dijkstra演算法的題目，(好像SPFA有點小小萬能的感覺?)
6) ??求負環一般使用SPFA演算法，方法是用一個cnt陣列記錄每個點到源點的邊數，一個點被更新一次就+1，一旦有點的邊數達到了n那就證明存在了負環，
代碼：
#include<bits/stdc++.h>
#define x first
#define y second
#define maxn 150010
using namespace std;
typedef pair<int, int> PII;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx,n,m,dist[maxn];
bool st[maxn];
void add(int a, int b, int c)
{
e[idx] = b; w[idx] = c; ne[idx] = h[a] ; h[a] = idx++;
}
int spfa(){
memset(dist,0x3f,sizeof(dist));
queue<int> q;
dist[1] = 0;
q.push(1);
st[1] = true;
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i=ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
memset(h,-1,sizeof(h));
cin >> n >> m;
for(int i = 1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
add(a, b, c);
}
int ans = spfa();
if(ans == 0x3f3f3f3f) cout << "impossible";
else cout << ans;
return 0;
}
接下來介紹spfa是可以用來判斷是否存在負權回路的：
方法：統計當前每個點的最短路中所包含的邊數，如果某點的最短路所包含的邊數大于等于n，則也說明存在環
y總原話：
每次做一遍spfa()一定是正確的，但時間復雜度較高，可能會超時，初始時將所有點插入佇列中可以按如下方式理解：
在原圖的基礎上新建一個虛擬源點，從該點向其他所有點連一條權值為0的有向邊，（所以dist不用 初始化為0x3f3f3f3f）那么原圖有負環等價于新圖有負環，此時在新圖上做spfa，將虛擬源點加入佇列中，然后進行spfa的第一次迭代，這時會將所有點的距離更新并將所有點插入佇列中，執行到這一步，就等價于視頻中的做法了，那么視頻中的做法可以找到負環，等價于這次spfa可以找到負環，等價于新圖有負環，等價于原圖有負環，得證，
1、dist[x] 記錄虛擬源點到x的最短距離
2、cnt[x] 記錄當前x點到虛擬源點最短路的邊數，初始每個點到虛擬源點的距離為0，只要他能再走n步，即cnt[x] >= n，則表示該圖中一定存在負環，由于從虛擬源點到x至少經過n條邊時，則說明圖中至少有n + 1個點，表示一定有點是重復使用
3、若dist[j] > dist[t] + w[i],則表示從t點走到j點能夠讓權值變少，因此進行對該點j進行更新，并且對應cnt[j] = cnt[t] + 1,往前走一步
注意：該題是判斷是否存在負環，并非判斷是否存在從1開始的負環，因此需要將所有的點都加入佇列中，更新周圍的點；
代碼：
#include<bits/stdc++.h>
#define maxn 2010
#define maxm 10010
using namespace std;
int h[maxn],e[maxm],ne[maxm],w[maxm],dist[maxn],cnt[maxn],idx,n,m;
bool st[maxn];
void add(int a,int b ,int c){
e[idx] = b; w[idx] = c; ne[idx] = h[a] ; h[a] = idx++;
}
bool spfa()
{
queue<int> q;
for(int i = 1;i<=n; i++){
q.push(i);
st[i] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t] ;i!=-1;i=ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j]>=n) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m -- )
{
int x,y,z;
cin >> x >> y >> z;
add(x,y,z);
}
if(spfa()) cout << "Yes";
else cout << "No";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/445904.html
標籤：其他
上一篇：一文搞懂LSM-Tree
下一篇：Eolink介面管理工具應用