實(shí)例解析Bellman-ford和Spfa算法

周鑫 張晶

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

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

中圖分類(lèi)號(hào)：TP312? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）30-0079-03

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 前言

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

例題：如圖1所示，求1號(hào)頂點(diǎn)到其余各頂點(diǎn)的最短距離。

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

給出邊的順序如下表：

2 Bellman-Ford算法題解

用d數(shù)組來(lái)存儲(chǔ)1號(hào)頂點(diǎn)到其余各點(diǎn)的路徑值。

初始化如下表：

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

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

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

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

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

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

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

根據(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算法的一種隊(duì)列實(shí)現(xiàn)，為了減少了不必要的冗余計(jì)算，我們用一個(gè)隊(duì)列來(lái)維護(hù)。初始時(shí)將起始點(diǎn)加入隊(duì)列，每次從隊(duì)列中取出隊(duì)首元素，并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，并將松弛成功的頂點(diǎn)入隊(duì)，直到隊(duì)列為空時(shí)算法結(jié)束。

針對(duì)本例題的具體實(shí)現(xiàn)過(guò)程如下：

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

首先源點(diǎn)1入隊(duì)，當(dāng)隊(duì)列非空時(shí)：

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

松弛以后，2和3兩個(gè)頂點(diǎn)的最短路徑估值變小，而這兩個(gè)點(diǎn)隊(duì)列中都沒(méi)有，因此入隊(duì)。

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

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

隊(duì)首元素3出隊(duì)，但是以3為起點(diǎn)沒(méi)有出邊，因此此時(shí)無(wú)松弛操作。

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

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

完整代碼如下：

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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