C++圖論之Bellman-Ford算法和SPFA算法的實(shí)現(xiàn)
給定一張有向圖,若對(duì)于圖中的某一條邊(x,y,z),有dist[y]≤dist[x]+z成立,則稱該邊滿足三角形不等式。如果所有邊都滿足三角形不等式,則dist數(shù)組就是所求的最短路。
Bellman-Ford算法
(x,y,z)表示的是一條從 x 出發(fā), 到達(dá) y ,長(zhǎng)度為 z 的有向邊。
首先介紹基于迭代的Bellman-Ford算法,它的流程如下:
1.掃描所有邊(x,y,z),若dist[y]>dist[x]+z, 則用dist[x]+z更新dist[y]
2.重復(fù)上述操作,直到?jīng)]有更新操作發(fā)生。
Bellman-Ford算法的時(shí)間復(fù)雜度是O(nm)
通過(guò)Bellman-Ford算法我們可以求解有邊數(shù)限制的最短路問(wèn)題。
例題:AcWing 853. 有邊數(shù)限制的最短路
算法步驟
初始化 dist 數(shù)組為正無(wú)窮, dist[1] = 0
(外重循環(huán))循環(huán) i 從 1 到 n ,遍歷 n 次表示:是不經(jīng)過(guò)超過(guò) 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)行一個(gè)備份,這樣防止每次更新的時(shí)候出現(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 ++ ) // 不超過(guò)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算法在國(guó)際上通稱為“隊(duì)列優(yōu)化的“Bellman-Ford算法”。
SPFA算法的流程如下:
1.建立一個(gè)隊(duì)列,起初隊(duì)列中只含有起點(diǎn)1
2.取出頭結(jié)點(diǎn) x ,掃描它的所有出邊(x,y,z),若dist[y]>dist[x]+z,則使dist[y]用dist[x]+z來(lái)更新。同時(shí)若y不再隊(duì)列中,則將y入隊(duì)
在任意時(shí)刻,該算法的隊(duì)列都保持了該拓展的節(jié)點(diǎn)。每次入隊(duì)都相當(dāng)于完成了一次 dist 數(shù)組的更新操作,使其滿足三角不等式。一個(gè)節(jié)點(diǎn)可能會(huì)入隊(duì)、出隊(duì)多次。最終,圖中所有的結(jié)點(diǎn)全部收斂到全部滿足三角不等式的狀態(tài)。
這個(gè)隊(duì)列避免了對(duì)Bellman-Ford算法中不需要拓展的多余結(jié)點(diǎn)的冗余掃描,在隨機(jī)圖上的運(yùn)行效率O(km)級(jí)別,其中 k 是一個(gè)很小的常數(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算法的資料請(qǐng)關(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ù)字),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語(yǔ)言實(shí)現(xiàn)“幸運(yùn)數(shù)”的實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)“幸運(yùn)數(shù)”的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07C語(yǔ)言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06C語(yǔ)言大廠面試技巧及strcpy()函數(shù)示例詳解
這篇文章主要為大家介紹了C語(yǔ)言面試技巧,以strcpy()函數(shù)為示例進(jìn)行分析詳解,有需要沖刺大廠的朋友們可以借鑒參考下,希望能夠有所幫助2021-11-11使用kendynet構(gòu)建異步redis訪問(wèn)服務(wù)
這篇文章主要介紹了在kendynet上寫(xiě)的一個(gè)簡(jiǎn)單的redis異步訪問(wèn)接口,大家參考使用吧2014-01-01C++實(shí)現(xiàn)四叉樹(shù)效果(附源碼下載)
這篇文章主要介紹了C++實(shí)現(xiàn)四叉樹(shù)效果(附源碼下載),非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2017-03-03淺談C++的語(yǔ)句語(yǔ)法與強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換
這篇文章主要介紹了淺談C++的語(yǔ)句語(yǔ)法與強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09適合初學(xué)者的C語(yǔ)言轉(zhuǎn)義字符講解
轉(zhuǎn)義字符是很多程序語(yǔ)言、數(shù)據(jù)格式和通信協(xié)議的形式文法的一部分。對(duì)于一個(gè)給定的字母表,一個(gè)轉(zhuǎn)義字符的目的是開(kāi)始一個(gè)字符序列,使得轉(zhuǎn)義字符開(kāi)頭的該字符序列具有不同于該字符序列單獨(dú)出現(xiàn)(沒(méi)有轉(zhuǎn)義字符開(kāi)頭)時(shí)的語(yǔ)義。因此轉(zhuǎn)義字符開(kāi)頭的字符序列被叫做轉(zhuǎn)義序列2022-04-04