【最短路徑】 SPFA演算法
上一期介紹到了SPFA演算法,只是一筆帶過,這一期讓我們詳細的介紹一下SPFA。
1 SPFA原理介紹
SPFA演算法和dijkstra演算法特別像,總感覺自己講的不行,同學說我的部落格很辣雞,推薦一個視訊講解,想看點 這裡 ,演算法思路如下:
1)和dijkstra一樣初始化,定義一個dis[ ]陣列,除了源點賦成0之外其它點都賦成正無窮,然後定義一個佇列q。
2)把佇列q的隊首元素取出,標誌為不在隊中,將其作為中繼點對這個隊首元素的所有出邊進行鬆弛操作(不知道鬆弛操作請看這裡),修改完dis值後,判斷每一個修改過dis值的元素是否在佇列q中,如果不在,就放入隊尾;然後判斷這個數入隊的次數,如果大於n(n為點的個數),那就說明出現了負權迴路,演算法結束,否則繼續。
3)不斷迴圈,直到佇列為空。
2 實現過程中的一些問題
- question:怎麼標誌出隊?
answer:可以定義一個vis[ ]陣列,最開始全部為0,表示都不在佇列中,每入隊一個元素x,就把vis[x]賦成1,每出隊一個元素就賦值成0。
- question:怎麼判斷一個數入隊次數?
answer:可以定義一個num[ ]陣列,每入隊一個元素x,就num[x]++;這個可以不寫,因為題目一般不會出現負權迴路。
- question:怎麼判斷佇列為空?
answer:最流行的寫法是while(q.empty()),但是不太好理解,我一般會寫成while(s.size()),和前一句意思相同。
3 圖解演示
//這個圖解做了一上午,可能講的不好,不喜勿噴
4 程式碼奉上:
1 void SPFA() 2 { 3for(int i=1;i<=n;i++) 4dis[i]=inf; 5queue<int>q; 6q.push(1);vis[1]=1;dis[1]=0; 7while(q.size()) 8{ 9x=q.front();q.pop();vis[x]=0; 10for(int i=head[x];i;i=a[i].next) 11{ 12int s=a[i].to; 13if(dis[s]>dis[x]+a[i].cost) 14{ 15dis[s]=dis[x]+a[i].cost; 16if(vis[s]==0) 17{ 18vis[s]=1; 19q.push(s); 20} 21} 22} 23} 24 }