實例解析Bellman-ford和Spfa算法

周鑫 張晶

摘要：Bellman-ford和Spfa是解決最短路問題的基本算法，是信息學(xué)奧賽教學(xué)的基本內(nèi)容。由于算法抽象性和邏輯性強，教學(xué)過程中學(xué)生對其基本原理、實現(xiàn)過程理解困難，導(dǎo)致無法靈活運用解決問題。該文旨在用具體實例結(jié)合圖表對算法執(zhí)行過程進行詳細解析，深刻剖析了算法的優(yōu)化原理，有效解決了學(xué)生理解和應(yīng)用困難的問題。

關(guān)鍵詞：Bellman-ford;Spfa;算法解析

中圖分類號：TP312? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）30-0079-03

開放科學(xué)（資源服務(wù)）標識碼（OSID）：

1 前言

Bellman-Ford算法由查理德·貝爾曼和萊斯特·福特創(chuàng)立的，其基本思想是利用松弛原理反復(fù)對邊集中的每條邊進行松弛迭代操作，同時更新頂點集合中每個頂點的最短路徑值并記錄其最短路徑上的前驅(qū)結(jié)點，達到收斂時停止迭代操作[1]。由于反復(fù)對邊集中的每條邊進行松弛，因此產(chǎn)生了很多冗余的松弛操作，造成時間復(fù)雜度較高。Spfa算法針對這一問題進行了優(yōu)化，其核心思想是用FIFO隊列保存已經(jīng)被松弛過的頂點，只處理入隊的頂點，并且不斷迭代以求得最短路徑。因此，深刻理解Bellman-Ford算法有助于充分理解和應(yīng)用Spfa算法解決實際問題[2]。下面我們用具體實例來展開探討這兩個算法的實現(xiàn)過程。

例題：如圖1所示，求1號頂點到其余各頂點的最短距離。

我們用d 數(shù)組記錄起點到其余各點的最短路徑值，用s、e、t三個數(shù)組來存儲邊的信息。例如第i條邊存儲在s[i]、e[i]、t[i]中，表示從頂點s[i]到e[i]這條邊的權(quán)值為t[i]。

給出邊的順序如下表：

2 Bellman-Ford算法題解

用d數(shù)組來存儲1號頂點到其余各點的路徑值。

初始化如下表：

根據(jù)邊給出的順序，先處理第一條邊“2-4-3”即判斷一下d[4]是否大于d[2]+3，由于此時d[4]和d[2]都是無窮大，因此這條邊松弛失敗。接下來處理第二條邊“1-2-（-1）”， 我們發(fā)現(xiàn)d[2] > d[1] + （-1） ，通過這條邊可以使d[2]的值從∞變?yōu)?-1 ，所以這個點松弛成功。我們可以用同樣的方法來處理第三條邊到第七條邊，對所有的邊進行一遍松弛操作后的結(jié)果如下：

第一輪對所有邊進行松弛以后，結(jié)果如下表所示：

第二輪對所有邊進行松弛以后，結(jié)果如下表所示：

在這輪松弛中，通過“2 4 3”（2→4）這條邊，更新了1號頂點到4號頂點的距離（d[4]） 。這條邊在第一輪松弛失敗，卻在第二輪松弛成功。原因是在第一 輪松弛過后，1號頂點到2號頂點的距離（d[2]） 已經(jīng)發(fā)生了變化，這一輪再通過“2 4 3”（2-→4）這條邊進行松弛的時候，可以使1號頂點到4號頂點的距離（d[4]） 的值變小。也就是說，第一輪遍歷圖中所有邊進行松弛操作之后，得到的是起點“經(jīng)過一條邊”到達其余各點的最短路徑值。第二輪遍歷圖中所有邊進行松弛操作之后，得到的是從起點“至多經(jīng)過兩條邊”到達其余各點的最短路徑值。如果進行n-1輪的話，得到的就是起點“至多經(jīng)過n-1條邊”到達其余各頂點的最短路徑值。在一個含有n個頂點的圖中，由于任意兩點之間的最短路徑最多經(jīng)過n-1條邊，因此最多松弛n-1輪。

第三輪對所有邊進行松弛以后，結(jié)果如下表所示：

第四輪對所有邊松弛以后，結(jié)果如下表所示：

從第三輪開始，對所有邊進行松弛操作，發(fā)現(xiàn)沒有頂點需要更新，此時便可以提前結(jié)束遍歷，優(yōu)化效率。最后表中數(shù)據(jù)就是1號頂點到其余各點的最短路徑值。

根據(jù)以上分析本題完整代碼如下：

#include

const int maxd = 1e9;

using namespace std;

int main（）{

int s[100] ， e[100] ， t[100] ， d[100] ， n ， m ;

cin>>n>>m;

for（int i = 1 ; i <= m ; i ++）

cin>>s[i] >>e[i] >>t[i];

for（int i = 1 ; i <= n ; i ++）d[i] = maxd;

d[1] = 0;

while（1）{

bool upd=false;

for（int j = 1 ; j <= m ; j ++）{

if（d[e[j]] > d[s[j]] + t[j]）{

d[e[j]] = d[s[j]] + t[j];

upd=true;

}

}

if（upd==false） break;

}

for（int i = 1 ; i <= n ; i ++） cout<

return 0 ;

}

/*

5 7

2 4 3

1 2 -1

1 3 5

5 3 4

2 3 -2

2 5 6

4 5 2

*/

3 Spfa算法題解

Spfa是Bellman-Ford算法的一種隊列實現(xiàn)，為了減少了不必要的冗余計算，我們用一個隊列來維護。初始時將起始點加入隊列，每次從隊列中取出隊首元素，并對所有與他相鄰的點進行松弛，并將松弛成功的頂點入隊，直到隊列為空時算法結(jié)束。

針對本例題的具體實現(xiàn)過程如下：

首先建立起始點1到其余各點的最短路徑表格，d[i]表示起點1到i點的最短路徑值。

首先源點1入隊，當隊列非空時：

隊首元素1出隊，對以1為起點的所有邊的終點（2、3）進行松弛操作，此時路徑表格狀態(tài)為：

松弛以后，2和3兩個頂點的最短路徑估值變小，而這兩個點隊列中都沒有，因此入隊。

隊首元素2出隊，對以2為起點的所有邊的終點（3，4，5）依次進行松弛操作，此時路徑表格狀態(tài)為：

此時，3，4，5三個頂點的最短路徑估值變小，其中3這個點已經(jīng)在隊列中，不用入隊，4，5兩個點入隊。

隊首元素3出隊，但是以3為起點沒有出邊，因此此時無松弛操作。

隊首元素4出隊，對以4為起點的所有邊的終點（5）進行松弛，此時路徑表格狀態(tài)為：

隊首元素5出隊，但是以5為起點沒有出邊，此時無松弛操作，并且隊列已空，算法結(jié)束，表中數(shù)據(jù)便是頂點1到其余各點的最短路徑值。

完整代碼如下：

#include

using namespace std;

const int N=1e5+5;

int cnt，head[N]，d[N]，n，m，vis[N];

struct edge{

int v，nxt，w;

}a[N*2];

void addedge（int u，int v，int w）{

a[++cnt].v=v;

a[cnt].w=w;

a[cnt].nxt=head[u];

head[u]=cnt;

}

void spfa（int s）{

queueq;

memset（d，0x3f，sizeof（d））;

d[s]=0;

q.push（s）;

vis[s]=1;

while（！q.empty（））{

int now=q.front（）;

q.pop（）;

vis[now]=0;

for（int i=head[now];i;i=a[i].nxt）{

int to=a[i].v;

if（a[i].w+d[now]<=d[to]）{

d[to]=a[i].w+d[now];

if（！vis[to]）{

q.push（to）;

vis[to]=1;

}

}

}

}

}

int main（）{

cin>>n>>m;

for（int i=1;i<=m;i++）{

int x，y，w;

cin>>x>>y>>w;

addedge（x，y，w）;

}

spfa（1）;

for（int i=1;i<=n;i++）cout<

return 0;

}

/*

5 7

2 4 3

1 2 -1

1 3 5

5 3 4

2 3 -2

2 5 6

4 5 2

*/

4兩種算法的聯(lián)系和區(qū)別

Bellman-Ford 算法時間復(fù)雜度為 O （nm），最多需要執(zhí)行 n-1 次循環(huán)，如果執(zhí)行了n次循環(huán)，說明圖中含有負圈[3]。Spfa算法是為了改進Bellman-Ford算法的效率而提出來的，在最優(yōu)的情況下，每個節(jié)點只入隊一次，這時退化為廣度優(yōu)先搜索，在最壞情況下，每個節(jié)點都入隊 n-1 次，此時 Spfa 算法退化為 Bellman-Ford 算法，時間復(fù)雜度為 O（nm）。如果某個節(jié)點的入隊次數(shù)超過 n 次，說明圖中肯定含有負圈[4-5]。

由于這兩種算法均采用鄰接表的方式存儲邊的信息，因此他們的空間復(fù)雜度均為 O（m）。

它們都可以解決負權(quán)圖問題，并能夠判斷圖中是否含有負圈，都適用于稀疏圖。

由以上分析可以看出，Bellman-Ford算法可解決的問題Spfa算法也都適用。因此，奧賽解題中更常用Spfa算法。但是，Bellman-Ford算法思想精妙，是Spfa算法的前置知識，在學(xué)習中先理解Bellman-Ford算法更有利于對Spfa算法的理解和應(yīng)用。

參考文獻：

[1] 陳雨婕.用圖示法解析最短路徑算法[J].電腦知識與技術(shù)，2007，3（24）：54-56.

[2] 劉磊，王燕燕，申春，等.Bellman-Ford算法性能可移植的GPU并行優(yōu)化[J].吉林大學(xué)學(xué)報（工學(xué)版），2015，45（5）：1559-1564.

[3] 韓偉一.固定序Bellman-Ford算法的一個改進[J].哈爾濱工業(yè)大學(xué)學(xué)報，2014，46（11）：58-62，69.

[4] 段凡丁.關(guān)于最短路徑的SPFA快速算法[J].西南交通大學(xué)學(xué)報，1994，29（2）：207-212.

[5] 夏正冬，卜天明，張居陽.SPFA算法的分析及改進[J].計算機科學(xué)，2014，41（6）：180-184，213.

【通聯(lián)編輯：唐一東】