C++圖論之Bellman-Ford算法和SPFA算法的實(shí)現(xiàn)
給定一張有向圖,若對于圖中的某一條邊(x,y,z),有dist[y]≤dist[x]+z成立,則稱該邊滿足三角形不等式。如果所有邊都滿足三角形不等式,則dist數(shù)組就是所求的最短路。
Bellman-Ford算法
(x,y,z)表示的是一條從 x 出發(fā), 到達(dá) y ,長度為 z 的有向邊。
首先介紹基于迭代的Bellman-Ford算法,它的流程如下:
1.掃描所有邊(x,y,z),若dist[y]>dist[x]+z, 則用dist[x]+z更新dist[y]
2.重復(fù)上述操作,直到?jīng)]有更新操作發(fā)生。
Bellman-Ford算法的時間復(fù)雜度是O(nm)
通過Bellman-Ford算法我們可以求解有邊數(shù)限制的最短路問題。
例題:AcWing 853. 有邊數(shù)限制的最短路
算法步驟
初始化 dist 數(shù)組為正無窮, dist[1] = 0
(外重循環(huán))循環(huán) i 從 1 到 n ,遍歷 n 次表示:是不經(jīng)過超過 i 條邊到達(dá)終點(diǎn)的最短距離
(內(nèi)重循環(huán))循環(huán) i 從 1 到 m, 遍歷 m 條邊,把所有的邊都進(jìn)行松弛操作:
每次取出兩點(diǎn)以及以及連接他們的權(quán)重 (a,b,w)
用以下公式更新最短距離: dist[b]=min(dist[b],dist[a]+w)
注意點(diǎn):
需要把dist數(shù)組進(jìn)行一個備份,這樣防止每次更新的時候出現(xiàn)串聯(lián)
由于存在負(fù)權(quán)邊,所以 return -1 的條件是dist[n]>0x3f3f3f/2
代碼實(shí)現(xiàn)
#include <iostream> #include <cstring> using namespace std; const int N = 510, M = 10010; struct Edge { int a, b, w; }e[M]; // 存下每一條即可 int dist[N]; int back[N]; // 備份數(shù)組放置串聯(lián) int n, m, k; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for(int i = 0; i < k; i ++ ) // 不超過k條邊 { memcpy(back, dist, sizeof back); for(int j = 0; j < m; j ++ ) // 遍歷所有邊 { int a = e[j].a, b = e[j].b, w = e[j].w; dist[b] = min(dist[b], back[a] + w); } } } int main() { cin >> n >> m >> k; for(int i = 0; i < m; i ++ ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); e[i] = {a, b, w}; } bellman_ford(); if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else cout << dist[n] << endl; return 0; }
SPFA算法
SPFA算法在國際上通稱為“隊(duì)列優(yōu)化的“Bellman-Ford算法”。
SPFA算法的流程如下:
1.建立一個隊(duì)列,起初隊(duì)列中只含有起點(diǎn)1
2.取出頭結(jié)點(diǎn) x ,掃描它的所有出邊(x,y,z),若dist[y]>dist[x]+z,則使dist[y]用dist[x]+z來更新。同時若y不再隊(duì)列中,則將y入隊(duì)
在任意時刻,該算法的隊(duì)列都保持了該拓展的節(jié)點(diǎn)。每次入隊(duì)都相當(dāng)于完成了一次 dist 數(shù)組的更新操作,使其滿足三角不等式。一個節(jié)點(diǎn)可能會入隊(duì)、出隊(duì)多次。最終,圖中所有的結(jié)點(diǎn)全部收斂到全部滿足三角不等式的狀態(tài)。
這個隊(duì)列避免了對Bellman-Ford算法中不需要拓展的多余結(jié)點(diǎn)的冗余掃描,在隨機(jī)圖上的運(yùn)行效率O(km)級別,其中 k 是一個很小的常數(shù)。
代碼實(shí)現(xiàn)
SPFA求最短路
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 1e6 + 10; int n, m; int h[N], e[N], w[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ; } void spfa() { memset(dist, 0x3f, sizeof dist); queue<int> q; dist[1] = 0; st[1] = true; q.push(1); while(q.size()) { int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; ~i; 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; } } } } } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } spfa(); if(dist[n] == 0x3f3f3f3f) puts("impossible"); else printf("%d",dist[n]); return 0; }
以上就是C++圖論之Bellman-Ford算法和SPFA算法的實(shí)現(xiàn)的詳細(xì)內(nèi)容,更多關(guān)于C++ Bellman-Ford SPFA算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
linux內(nèi)核select/poll,epoll實(shí)現(xiàn)與區(qū)別
這篇文章主要介紹了linux內(nèi)核select/poll,epoll實(shí)現(xiàn)與區(qū)別,需要的朋友可以參考下2016-11-11C++實(shí)現(xiàn)LeetCode(65.驗(yàn)證數(shù)字)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(65.驗(yàn)證數(shù)字),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語言實(shí)現(xiàn)“幸運(yùn)數(shù)”的實(shí)例詳解
這篇文章主要介紹了C語言實(shí)現(xiàn)“幸運(yùn)數(shù)”的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07C語言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-06-06使用kendynet構(gòu)建異步redis訪問服務(wù)
這篇文章主要介紹了在kendynet上寫的一個簡單的redis異步訪問接口,大家參考使用吧2014-01-01淺談C++的語句語法與強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換
這篇文章主要介紹了淺談C++的語句語法與強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09