《算法設(shè)計(jì)與分析》課件第7章

第7章圖算法7.1圖的表示7.2廣度優(yōu)先搜索7.3

Dijkstra算法7.4

Bellman-Ford算法7.5

Floyd-Warshall算法

習(xí)題許多應(yīng)用問題可以歸結(jié)為圖模型上的問題。因而，我們可以用圖作為表示和求解問題的工具。例如，在航線圖中，圖中的頂點(diǎn)可以表示機(jī)場(chǎng)，邊可以表示飛行航線，邊上的權(quán)值則可能表示距離或費(fèi)用。在電路圖中，圖中的頂點(diǎn)表示邏輯門、寄存器、引腳或處理器，邊表示接線，邊上的權(quán)值可能表示接線長(zhǎng)度或傳輸延遲。在作業(yè)調(diào)度問題中，圖中的頂點(diǎn)表示作業(yè)，邊表示優(yōu)先關(guān)系，邊上的權(quán)值可能表示優(yōu)先級(jí)。在金融問題中，圖中的頂點(diǎn)表示股票或流通貨幣，邊表示交易或事務(wù)處理，邊上的權(quán)值可能表示費(fèi)用。表7-1列舉了不同應(yīng)用領(lǐng)域在圖模型中的意義。表7-1應(yīng)用領(lǐng)域與圖模型

7.1圖的表示

可以使用鄰接矩陣來表示一個(gè)圖。對(duì)于有n(=|V|)個(gè)頂點(diǎn)的圖，其鄰接矩陣的第(i，j)個(gè)元素為

其中，vi(i=1,…,n)為圖中頂點(diǎn)。對(duì)于一個(gè)無向圖，因?yàn)槠渲械拿織l邊{u，v}可從兩個(gè)方向看待，因而該鄰接矩陣是對(duì)稱的。這種表示的好處是可在常量時(shí)間內(nèi)檢查圖中是否存在某條邊，只需要訪問一次內(nèi)存。而矩陣需要O(n2)的空間。如果圖中的邊數(shù)不是很多，這種表示方式浪費(fèi)空間。圖的另一種表示方法是鄰接表表示法。這種方法只需要與邊數(shù)成正比的空間，由|V|個(gè)鏈表組成，每個(gè)頂點(diǎn)都有一個(gè)鏈表。頂點(diǎn)u的鏈表存放由u出發(fā)所指向的頂點(diǎn)，也就是說，存放(u，v)∈E的那些頂點(diǎn)v。因此，如果圖為有向圖，則每條邊只在一個(gè)鏈表中出現(xiàn)；如果圖為無向圖，則每條邊在兩個(gè)鏈表中出現(xiàn)。無論是哪種情況，數(shù)據(jù)結(jié)構(gòu)的總規(guī)模為O(|E|)。在這種情況下，檢查某條邊(u，v)不再為常量時(shí)間，因?yàn)檫@個(gè)過程需要查找u的鄰接表。但通過一個(gè)頂點(diǎn)的所有近鄰還是可以比較容易地完成這個(gè)過程。我們很快就可知，這個(gè)過程證明是圖算法中的一個(gè)很有用的操作。對(duì)于無向圖，這種表示是對(duì)稱的，當(dāng)且僅當(dāng)u在v的鄰接表中，v在u的鄰接表中。使用哪一種表示法，取決于頂點(diǎn)集|V|中頂點(diǎn)之間的關(guān)系、圖中的頂點(diǎn)數(shù)以及邊數(shù)|E|。|E|的規(guī)?？膳c|V|相當(dāng)或與|V|2相當(dāng)(所有邊可能相連)。如果是前者，則稱該圖是稀疏的，否則稱該圖是稠密的。我們將在后續(xù)的章節(jié)中看到，|E|與|V|之間的這個(gè)關(guān)系將會(huì)成為我們選擇合適圖算法的主要因素。

7.2廣度優(yōu)先搜索

廣度優(yōu)先搜索(BreadthFirstSearch，BFS)是圖搜索中最簡(jiǎn)單的算法之一，也是很多重要圖算法的基礎(chǔ)算法。Dijkstra單源點(diǎn)最短路徑算法就使用了與BFS類似的思想。

給定一個(gè)圖G=(V，E)以及一個(gè)稱為源點(diǎn)的特殊頂點(diǎn)s，BFS系統(tǒng)地探索圖G中的邊，找出由s可達(dá)的那些頂點(diǎn)。BFS計(jì)算出從s到每個(gè)可達(dá)頂點(diǎn)的距離(最少邊數(shù))。同時(shí)，還形成一棵根為s的廣度優(yōu)先樹，這棵樹中包括了由s可達(dá)的所有頂點(diǎn)。對(duì)于由s可達(dá)的任一頂點(diǎn)v，在這棵廣度優(yōu)先樹中從s到v的路徑對(duì)應(yīng)于圖G中從s到v的一條最短路徑，也就是說，包含了邊數(shù)最少的一條路徑。BFS算法對(duì)于有向圖和無向圖均適用。對(duì)于圖7-1，以結(jié)點(diǎn)a作為源點(diǎn)s，將該圖劃分為若干層：s自身，與s距離為1的那些頂點(diǎn)作為一層，與s距離為2的那些結(jié)點(diǎn)作為另一層，以此類推。一種簡(jiǎn)便的計(jì)算從s到其他頂點(diǎn)的距離的方法是逐層進(jìn)行計(jì)算。一旦計(jì)算出距離為0，1，2，…，d的那些頂點(diǎn)，就很容易確定出距離為d+1的頂點(diǎn)。這些頂點(diǎn)就是那些與距離為d的那層頂點(diǎn)相鄰的尚未被訪問的頂點(diǎn)。這就給出一個(gè)在任一給定時(shí)刻只有兩層是活躍的迭代算法：在某層d，其中的頂點(diǎn)完全被訪問過；在d+1層，要通過掃描第d層頂點(diǎn)的近鄰，來找出該層的頂點(diǎn)。圖7-1有向圖示例廣度優(yōu)先搜索直接實(shí)現(xiàn)了我們上述的過程。初始時(shí)，隊(duì)列Q中只含頂點(diǎn)s，即距離為0的頂點(diǎn)。對(duì)于后續(xù)距離d=1，2，3，…，在某時(shí)刻，隊(duì)列Q中只包含距離為d的所有頂點(diǎn)。隨著這些頂點(diǎn)被處理(執(zhí)行出隊(duì)操作)，其尚未被訪問的近鄰被插入到隊(duì)尾。圖7-2給出了訪問圖7-1中頂點(diǎn)時(shí)的當(dāng)前隊(duì)列，其中a為起始點(diǎn)，頂點(diǎn)按照字母順序排列。隊(duì)列Q中字母上方的數(shù)字表示起始點(diǎn)到該頂點(diǎn)的距離。而且圖7-2右邊的廣度優(yōu)先搜索樹包含了每個(gè)頂點(diǎn)最先被訪問時(shí)所通過的那些邊。由此可得，從a開始的每條路徑都是最短路徑。因此，這棵樹稱為最短路徑樹(shortestpathtree)。圖7-2圖7-1的廣度優(yōu)先隊(duì)列Q及其廣度優(yōu)先搜索樹廣度優(yōu)先搜索算法如下所示。

BFS(G,s)

1 foreachvertexv

V[G]//初始化到頂點(diǎn)v的最短路徑及前驅(qū)

2

do

d[v]

3

[v]

NIL

4 d[s]

0

5 Q

//初始化隊(duì)列Q

6 ENQUEUE(Q,s)

7 while

Q

//隊(duì)列中存在頂點(diǎn)

8

dou

DEQUEUE(Q)//摘取隊(duì)列中最小元素

9

foreachvertexv

Adj[u]//更新頂點(diǎn)v的最短路徑長(zhǎng)度

10 do

if

d[v]=

11

then

d[v]

d[u]+1

12

ENQUEUE(Q,v)以下分析算法的運(yùn)行時(shí)間。初始化后，第10行的測(cè)試保證每個(gè)頂點(diǎn)至多入隊(duì)一次，且至多出隊(duì)一次。入隊(duì)和出隊(duì)操作所需時(shí)間為常量時(shí)間O(1)，因而，隊(duì)列操作的總時(shí)間為O(V)。由于僅在頂點(diǎn)出隊(duì)時(shí)才掃描該頂點(diǎn)的鄰接表，因此，每個(gè)鄰接表至多被掃描一次。由于所有鄰接表的長(zhǎng)度之和為Θ(E)，因此掃描鄰接表所花費(fèi)的總時(shí)間為O(E)。初始化的開銷為O(V)。因此，BFS的總運(yùn)行時(shí)間為O(V+E)。由此可得，廣度優(yōu)先搜索算法的運(yùn)行時(shí)間為G的鄰接表表示規(guī)模的線性時(shí)間。

BFS算法的執(zhí)行過程如圖7-3所示。圖7-3

BFS算法的執(zhí)行過程

7.3

Dijkstra算法

給定加權(quán)有向圖G=(V，E)，定義權(quán)函數(shù)w為邊到其上實(shí)值的映射w：E→R。路徑p=〈v0，v1，…，vk〉上的權(quán)定義為這條路徑邊上的權(quán)值之和，即

定義從u到v的最短路徑權(quán)值為

因此，從u到v的最短路徑定義為u到v且滿足w(p)=δ(u,v)的路徑p。

1.最短路徑問題的最優(yōu)子結(jié)構(gòu)

最短路徑算法具有這樣一個(gè)性質(zhì)：兩個(gè)頂點(diǎn)之間的最短路徑包括這條路徑上其他頂點(diǎn)之間的最短路徑。這個(gè)最優(yōu)子結(jié)構(gòu)性質(zhì)應(yīng)用了動(dòng)態(tài)規(guī)劃和貪心算法的特點(diǎn)。Dijkstra算法是一個(gè)貪心算法。引理7.1更準(zhǔn)確地闡述了最短路徑問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。

引理7.1最短路徑的子路徑是最短路徑。

證明給定權(quán)函數(shù)為w：E→R的加權(quán)有向圖G=(V,E)，設(shè)p=〈v1,v2,…,vk〉是從頂點(diǎn)v1到頂點(diǎn)vk的最短路徑，對(duì)于任意滿足1≤i≤j≤k的頂點(diǎn)i和j，設(shè)pij=〈vi,vi+1,…,vj〉為p的從頂點(diǎn)vi到頂點(diǎn)vj的子路徑，那么，pij是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。

2.權(quán)值為負(fù)的邊與回路

在單源點(diǎn)最短路徑問題的例子中，可能存在權(quán)值為負(fù)的邊。如果圖G=(V,E)不含從源點(diǎn)s可達(dá)的負(fù)權(quán)值回路，那么對(duì)于所有v∈V，即使最短路徑權(quán)值為負(fù)，最短路徑權(quán)值d(s,v)的定義依然成立。然而，如果圖G中存在從源點(diǎn)s可達(dá)的負(fù)權(quán)值回路，那么對(duì)于所有v∈V，最短路徑權(quán)值d(s,v)的定義就不能成立。在這種情況下，不存在從源點(diǎn)s到這個(gè)回路

上頂點(diǎn)的最短路徑。如果G中存在從源點(diǎn)s到v的負(fù)權(quán)值回路，則定義d(s,v)=－∞，如圖7-4所示。每個(gè)頂點(diǎn)上的數(shù)字表示從源點(diǎn)s到該點(diǎn)的最短路徑權(quán)值，頂點(diǎn)e和f形成由s可達(dá)的負(fù)權(quán)值回路，因此，它們的最短路徑權(quán)值為－∞。而頂點(diǎn)g可由最短路徑權(quán)值為－∞的頂點(diǎn)到達(dá)，因此，它的最短路徑權(quán)值也為－∞。頂點(diǎn)h、i和j由s不可達(dá)，因此即使它們位于負(fù)權(quán)值的回路上，它們的最短路徑權(quán)值也為∞。圖7-4有向圖中的負(fù)權(quán)值邊

3.最短路徑表示與松弛操作

常常需要計(jì)算最短路徑的權(quán)值，而且還要找出組成最短路徑上的那些頂點(diǎn)。給定圖G=(V,E)，用π［v］表示頂點(diǎn)v∈V的前驅(qū)(predecessor)，它是一個(gè)頂點(diǎn)或?yàn)镹IL。在最短路徑算法的執(zhí)行過程中，無需通過π值表明最短路徑，主要關(guān)注π值所導(dǎo)出的前驅(qū)子圖Gπ=(Vπ,Eπ)即可。定義頂點(diǎn)集合Vπ如下：

Vπ={v∈V：π［v］≠NIL}∪{s}

有向邊集Eπ定義為由Vπ中頂點(diǎn)的π值所導(dǎo)出的邊集，即

Eπ={(π［v］,v)∈E：v∈Vπ－{s}}算法所產(chǎn)生的π值具有如下性質(zhì)：在算法終止時(shí)，Gπ就是最短路徑樹。這棵樹以源點(diǎn)s為根，包含了由s可達(dá)的每個(gè)頂點(diǎn)的一條最短路徑。因此，以s為根的最短路徑樹是有向子圖G′=(V′,E′)，其中V′

V，E′

E，滿足：

(1)V′是G中由s可達(dá)的頂點(diǎn)集合。

(2)G′形成以s為根的有根樹。

(3)對(duì)于所有v∈V′，G′中從s到v的最短路徑就是G中從s到v的最短路徑。最短路徑不必惟一，最短路徑樹也不必惟一。算法的主要思想是反復(fù)應(yīng)用松弛(relaxation)操作。對(duì)于每個(gè)頂點(diǎn)v∈V，維持d［v］，這是從源點(diǎn)s到頂點(diǎn)v的最短路徑權(quán)值的上界。稱d［v］為最短路徑估值。算法的初始化過程如下：

INITIALIZE-SINGLE-SOURCE(G,s)

1 foreachvertexv

V[G]//初始化到頂點(diǎn)v的最短路徑及前驅(qū)

2

do

d[v]

3

[v]

NIL

4 d[s]

0

初始化之后，對(duì)于所有v∈V，有π［v］=NIL；對(duì)于v∈Vπ－{s}，有d［s］=0和d［v］←∞。一條邊(u,v)是否需要松弛，取決于對(duì)這條邊的測(cè)試結(jié)果。如果能夠通過頂點(diǎn)u改進(jìn)目前源點(diǎn)到頂點(diǎn)v的最短路徑，則對(duì)d［v］和π［v］進(jìn)行更新。因此，松弛操作會(huì)使最短路徑估值d［v］下降，并對(duì)頂點(diǎn)v的前驅(qū)π［v］進(jìn)行更新。過程RELAX實(shí)現(xiàn)對(duì)邊(u,v)的松弛：

RELAX(u,v,w)//對(duì)更小權(quán)值頂點(diǎn)的最短路徑長(zhǎng)度進(jìn)行更新

1 ifd[v]>d[u]+w(u,v)

2 thend[v]

d[u]+w(u,v)

3

[v]

u

4.Dijkstra算法

在Dijkstra算法中，假定有加權(quán)有向圖G，且對(duì)于每條邊(u,v)∈E，w(u,v)≥0，即所有邊上的權(quán)值非負(fù)。算法維持頂點(diǎn)集合S，從源點(diǎn)到該集合中頂點(diǎn)的最短路徑已被確定。算法不斷從集合V－S中選出具有最短路徑估值的頂點(diǎn)u∈V－S，并將u添加到S中，松弛所有離開u的邊。在算法實(shí)現(xiàn)中，利用頂點(diǎn)的最小優(yōu)先隊(duì)列Q作為數(shù)據(jù)結(jié)構(gòu)，以d值為優(yōu)先級(jí)。

第1、2行分別初始化d、π、集合S(為空)。第3行對(duì)最小優(yōu)先隊(duì)列Q進(jìn)行初始化，使其包含所有頂點(diǎn)。在第4～8行的while循環(huán)每次迭代的開始，算法維持不變式Q=V－S。由于初始化S=，執(zhí)行第3行之后，循環(huán)不變式為真。在每次執(zhí)行4～8行的while循環(huán)體時(shí)，從Q=V－S中摘取一個(gè)頂點(diǎn)u，并添加到集合S中，因而保持循環(huán)不變式。第一次執(zhí)行while循環(huán)時(shí)，u=s。因而，頂點(diǎn)u是V－S中最短路徑估值最小的頂點(diǎn)。如果到v的最短路徑可以通過頂點(diǎn)u得到改進(jìn)，則在第7和第8行中，將離開u的邊(u,v)松弛，即對(duì)d［v］的估值和π［v］進(jìn)行更新。在第3行之后，Q中不再插入頂點(diǎn)，每個(gè)頂點(diǎn)只從Q中被摘取一次，只向S中添加一次，因此，第4～8行的while循環(huán)恰好迭代|V|次。DIJKSTRA(G,w,s)

1 INITIALIZE-SINGLE-SOURCE(G,s)//初始化到頂點(diǎn)v的最短路徑及前驅(qū)

2 S

3 Q

V[G]

//初始化隊(duì)列Q

4 while

Q

//隊(duì)列中存在頂點(diǎn)

5

dou

EXTRACT-MIN(Q)//摘取隊(duì)列中最小元素

6 S

S

{u}

7

foreachvertexv

Adj[u]//更新頂點(diǎn)v的最短路徑長(zhǎng)度

8

doRELAX(u,v,w)Dijkstra算法的執(zhí)行過程如圖7-5所示。圖7-5

Dijkstra算法的執(zhí)行過程

5.Dijkstra算法的貪心策略

由于Dijkstra算法總是選擇V－S中最輕或者最近頂點(diǎn)添加到集合S中，因此稱該算法利用了貪心策略。盡管貪心策略并不一定會(huì)產(chǎn)生最優(yōu)解，但是正如在定理4.7及推論4.8中所表明的那樣，Dijkstra算法可以計(jì)算頂點(diǎn)的最短路徑。證明的關(guān)鍵是每次向集合S中添加頂點(diǎn)u時(shí)，d［u］=δ(s,u)。我們?cè)谧C明Dijkstra算法的正確性時(shí)，使用圖7-6進(jìn)行說明。圖7-6

Dijkstra算法的證明圖示

定理7.2

Dijkstra算法的正確性。

給定加權(quán)有向圖G=(V,E)，以及非負(fù)權(quán)函數(shù)w和源點(diǎn)s。如果對(duì)該圖運(yùn)行Dijkstra算法，則在算法終止時(shí)，對(duì)于所有頂點(diǎn)u∈V，有d［u］=δ(s,u)。

證明：利用循環(huán)不變式：對(duì)于每一頂點(diǎn)v∈S，執(zhí)行第6～10行的while循環(huán)的每次迭代時(shí)，有d［v］=δ(s,v)。

只要證明，對(duì)于每一頂點(diǎn)u∈S，當(dāng)u添加到集合S時(shí)，d［u］=δ(s,u)即可。一旦證明d［u］=δ(s,u)，就可以根據(jù)上界性質(zhì)證明此后的所有時(shí)刻，這個(gè)等式都成立。初始時(shí)：S=，因而，循環(huán)不變式平凡成立。

維持時(shí)：希望證明，在每次迭代過程中，添加到集合S中的頂點(diǎn)滿足d［u］=δ(s,u)。用反證法證明。設(shè)u是添加到S中滿足d［u］≠δ(s,u)的第一個(gè)頂點(diǎn)。要證明while循

環(huán)迭代的開始，u被添加到S中，通過檢查此時(shí)從s到u的最短路徑，導(dǎo)出d［u］=δ(s,u)的矛盾。因?yàn)閟是添加到S中的第一個(gè)頂點(diǎn)，且d［s］=δ(s,s)=0，因而必有u≠s。由于u≠s,可以得出就在u被添加到S中之前，S≠。因而，一定存在從s到u的路徑，否則，如果路徑不存在，則有d［u］=δ(s,u)=∞，這與假設(shè)d［u］≠δ(s,u)矛盾。因?yàn)閺膕到u至少存在一條路徑，設(shè)這條路徑為p。在將頂點(diǎn)u添加到集合S中之前，路徑p將S中的頂點(diǎn)s與V－S中的某個(gè)頂點(diǎn)相連。考慮路徑p上滿足y∈V－S的第一個(gè)頂點(diǎn)y，設(shè)x∈S是y的前驅(qū)，參考圖7-6，路徑p可以分解為 。

首先證明斷言，當(dāng)u添加到S中時(shí)，d［y］=δ(s,y)。觀察可見x∈S。由于u是插入集合S且滿足d［u］≠δ(s,u)的第一個(gè)頂點(diǎn)，當(dāng)x被添加到S中時(shí)，則有d［x］=δ(s,x)。此時(shí)，邊(x,y)被松弛。由收斂性質(zhì)(如果s～>u→v是G中的一條最短路徑，u,v∈V，且在松弛邊(u,v)之前的任何時(shí)刻，d［u］=δ(s,u)，那么，此后的任意時(shí)刻，d［v］=δ(s,v))，聲明成立?，F(xiàn)在證明d［u］=δ(s,u)，導(dǎo)出矛盾。因?yàn)樵趶膕到u的最短路徑上，y出現(xiàn)在u之前，且所有邊的權(quán)值非負(fù)(注意p2上的那些權(quán)值)，則有δ(s,y)≤δ(s,u)。因此有

d［y］=δ(s,y)≤δ(s,u)≤d［u］//由上界性質(zhì) (7.1)

推論7.3給定加權(quán)有向圖G=(V,E)，以及非負(fù)權(quán)函數(shù)w和源點(diǎn)s。如果對(duì)該圖運(yùn)行Dijkstra算法，則在算法終止時(shí)，前驅(qū)子圖Gπ是一棵根為s的最短路徑樹。

證明：由定理7.2和前驅(qū)子圖的性質(zhì)直接得到。證畢。

6.Dijkstra算法的運(yùn)行時(shí)間

Dijkstra算法通過調(diào)用3個(gè)優(yōu)先隊(duì)列的操作,來維持最小優(yōu)先隊(duì)列Q。這3個(gè)操作是INSERT(第3行中隱含)、EXTRACT-MIN(第5行)和DECREASE-KEY(隱含在第8行的RELAX中)。每個(gè)頂點(diǎn)調(diào)用一次INSERT，同樣EXTRACT-MIN也被每個(gè)頂點(diǎn)調(diào)用一次。因?yàn)槊總€(gè)頂點(diǎn)v∈V只向集合S中添加一次，所以在算法運(yùn)行過程中，第7、8行的for循環(huán)只對(duì)鄰接表Adj［v］中的每條邊檢查一次。鄰接表中邊的總數(shù)為|E|，因此，這個(gè)for循環(huán)總共迭代|E|次，總共進(jìn)行至多|E|次的DECREASE-KEY操作。

Dijkstra算法的運(yùn)行時(shí)間取決于最小優(yōu)先隊(duì)列如何實(shí)現(xiàn)?？紤]這樣一種情況，利用從1到|V|的頂點(diǎn)編號(hào)維持優(yōu)先隊(duì)列Q。將d［v］存儲(chǔ)在數(shù)組的第v個(gè)元素中。每個(gè)INSERT和

DECREASE-KEY操作需要O(1)的時(shí)間。每個(gè)EXTRACT-MIN操作需要O(V)的時(shí)間，因?yàn)樾枰檎艺麄€(gè)數(shù)組。因此算法的運(yùn)行時(shí)間為O(V2+E)=O(V2)。

如果G是稀疏圖，可用二叉堆實(shí)現(xiàn)優(yōu)先隊(duì)列。每個(gè)EXTRACT-MIN操作需要O(lbV)的時(shí)間，共有|V|個(gè)這樣的操作。建立二叉堆的時(shí)間為O(V)，每個(gè)DECREASE-KEY操作需要O(lbV)的時(shí)間,至多有|V|個(gè)這樣的操作,因此算法的運(yùn)行時(shí)間為O((V+E)lbV)，如果所有頂點(diǎn)均從源點(diǎn)s可達(dá)，則算法的運(yùn)行時(shí)間為O(ElbV)。如果用斐波那契堆實(shí)現(xiàn)優(yōu)先隊(duì)列，則可得算法的運(yùn)行時(shí)間為O(VlbV+E)。這是因?yàn)閨V|個(gè)EXTRACT-MIN操作的平攤開銷為O(lbV)。每個(gè)DECREASE-KEY操作的調(diào)用只需O(1)的平攤開銷，這樣的操作至多有|E|個(gè)。

由以上分析可得，Dijkstra算法的運(yùn)行時(shí)間T=Θ(V)TEXTRACT-MIN+Θ(E)TDECREASE-KEY主要取決于所使用的優(yōu)先隊(duì)列Q的實(shí)現(xiàn)。表7-2給出了基于上述三種實(shí)現(xiàn)時(shí)的Dijkstra算法的運(yùn)行時(shí)間。表7-2不同實(shí)現(xiàn)時(shí)的Dijkstra算法的運(yùn)行時(shí)間 7.4

Bellman-Ford算法

在Dijkstra算法中，從起始點(diǎn)s到任何頂點(diǎn)v的最短路徑必定只通過那些比到頂點(diǎn)v更近的頂點(diǎn)。當(dāng)邊上的權(quán)值為負(fù)時(shí)，這一結(jié)論不再成立。在圖7-7中，從s到v的最短路徑通

過u，而頂點(diǎn)u距離s的最短路徑要長(zhǎng)。圖7-7帶有負(fù)權(quán)值邊的圖松弛操作具有如下性質(zhì)：

(1)這個(gè)松弛操作給出了如下情況下到v的正確距離，此時(shí)u是到v的這條最短路徑上倒數(shù)第2個(gè)頂點(diǎn)且d［u］也是正確距離。

(2)松弛操作將不再使d［v］更小，從這個(gè)意義上講，它是安全的。例如，其他松弛操作也不會(huì)對(duì)已有結(jié)果產(chǎn)生影響。這個(gè)操作非常有用。如果仔細(xì)斟酌，就可以設(shè)置出正確距離。實(shí)際上，也可將Dijkstra算法簡(jiǎn)單地看做一系列的松弛過程。如上所述，這個(gè)松弛序列并不適合于帶有負(fù)權(quán)值邊的圖，那么是否存在適合于負(fù)權(quán)值邊的其他序列呢？為了得到這個(gè)序列所具備的屬性，我們選取頂點(diǎn)t，并觀察從s到頂點(diǎn)t的最短路徑：這條路徑上至多包含|V|－1條邊。如果執(zhí)行的松弛序列包含(s，u1)，(u1，u2)，(u2，u3)，…，(uk，t)，那么由第一個(gè)性質(zhì)可正確計(jì)算出到t的距離。這些邊上出現(xiàn)的其他松弛操作是不重要的，因?yàn)檫@些松弛是安全的。

然而，如果預(yù)先并不知道最短路徑，怎樣才能確信以正確的順序松弛了正確的邊呢？這里給出一種簡(jiǎn)單的解決方案：簡(jiǎn)單地對(duì)所有邊松弛|V|－1次。以下給出的算法具有O(VE)

的運(yùn)行時(shí)間，稱為Bellman-Ford算法。BELLMAN-FORD(G,w,s)

1 INITIALIZE-SINGLE-SOURCE(G,s)

2 fori

1to|V[G]|－1

3 doforeachedge

(u,v)

E[G]

4

doRELAX(u,v,w)

5 foreachedge

(u,v)

E[G]

6 doif

d[v]>d[u]+w(u,v)

7thenreturnFALSE

8returnTRUE實(shí)際中，很多圖的最短路徑中的最大邊數(shù)遠(yuǎn)遠(yuǎn)小于|V|－1，這使得所需的松弛操作輪數(shù)大為減少。因此，增加一個(gè)對(duì)最短路徑算法的檢查具有實(shí)際意義，它可以將沒有松弛出現(xiàn)的那些輪很快地終止。

Bellman-Ford算法的執(zhí)行過程(i=1)如圖7-8所示。圖7-8

Bellman-Ford算法的執(zhí)行過程(i=1) 7.5

Floyd-Warshall算法

如果k是路徑p上具有最大編號(hào)的中間頂點(diǎn)，那么將路徑p分為如圖7-9所示的兩條路徑p1和p2。由最優(yōu)子結(jié)構(gòu)性質(zhì)，p1是所有中間頂點(diǎn)均在{1，2，…，k－1}中的從頂點(diǎn)i到k的一條最短路徑。類似地，p2是所有中間頂點(diǎn)均在{1,2，

…，k－1}中的從頂點(diǎn)k到j(luò)的一條最短路徑。圖7-9從頂點(diǎn)i到j(luò)的最短路徑p從以上分析可得，我們可以定義最短路徑估值的遞歸公式。令d(i，j，k)表示其所有中間頂點(diǎn)均在{1，2，…，k}中的從頂點(diǎn)i到j(luò)的最短路徑的長(zhǎng)度。初始時(shí)，如果頂點(diǎn)i和j之間有邊相連，則d(i，j，0)=wij；否則d(i,j,0)=∞。它表示在不含編號(hào)k大于0的中間頂點(diǎn)的從頂點(diǎn)i到j(luò)的最短路徑上，不包含任何中間頂點(diǎn)。此時(shí)這樣的路徑至多包含一條邊。以上討論可得最短路徑估值的遞歸定義對(duì)于任何路徑，由于其所有中間頂點(diǎn)均在集合{1，2，…，k}中，因而d(i，j，n)給出每一對(duì)頂點(diǎn)i，j之間的最短路徑，即d(i，j，n)=δ(i，j)，其中i，j∈V。

FLOYD-WARSHALL(W)

1 fori

1to|V[G]|

2

doforj

1to|V[G]|

3

do

d(i,j,0)

4 forall(i,j)

E[G]

5

do

d(i,j,0)

wij

6 fork

1to|V[G]| 7

dofori

1to|V[G]|

8

do

forj

1to|V[G]|

9 do

d(i,j,k)

min(d(i,j,k－1),d(i,k,k－1)+d(k,j,k－1))

10 return

d(i,j,n)

算法的執(zhí)行過程如圖7-10所示。圖7-10

Floyd-Warshall算法的執(zhí)行過程

習(xí)題

7-1假設(shè)在圖7-11上運(yùn)行Dijkstra算法，源點(diǎn)為a。

(1)在有向圖7-11上，運(yùn)行Dijkstra算法，以a作為源點(diǎn)。要求顯示while循環(huán)的每次迭代后d和π的值，以及集合S中的頂點(diǎn)。

(2)給出最終的最短路徑樹。

7-2在有向圖7-12上運(yùn)行Dijkstra算法，首先以s作為源點(diǎn)，然后以z作為源點(diǎn)。要求顯示while循環(huán)的每次迭代后d和π的值，以及集合S中的頂點(diǎn)。圖7-12習(xí)題7-2圖

7-3假定將Dijkstra算法中的第(4)行變?yōu)?/p>

4

while|Q|>1[HT5K]

所做的改變會(huì)使while循環(huán)執(zhí)行|V|－1，而不是|V|次。試問這個(gè)算法是否正確。

7-4假設(shè)在圖7-13上運(yùn)行Bellman-Ford算法，源點(diǎn)為z。在每一遍松弛邊的過程中，順序?yàn)?t，x)，(t，y)，(t，z)，(x，t)，(y，x)，(y，z)，(z，x)，(z，s)，(s，t)，(s，y)。

(1)在圖7-13上運(yùn)行Bellman-Ford算法，給出類似圖7-8執(zhí)行該算法第一遍后的過程，并給出d值和π值。

(2)將邊(z，x)上的權(quán)值變?yōu)?，以s為源點(diǎn)，重做(1)。圖7-13習(xí)題7-3圖

7-5給出一個(gè)含有負(fù)權(quán)值邊的有向圖的簡(jiǎn)單實(shí)例，該圖使Dijkstra算法的運(yùn)行產(chǎn)生錯(cuò)誤的結(jié)果。當(dāng)允許圖中存在負(fù)權(quán)值邊時(shí)，為什么定理7.2的證明不能成立？

7-6給定有向圖G=(V，E)，對(duì)于每條邊(u，v)∈E，關(guān)聯(lián)一個(gè)值r(u，v)，且0≤r(u，v)≤1。該值表示從頂點(diǎn)u到頂點(diǎn)v的信道的可靠性。可以將r(u，v)的意義解釋為u到v的信道不發(fā)生故障的概率，并假設(shè)這些概率是獨(dú)立的。試設(shè)計(jì)一有效算法，找出兩個(gè)給定頂點(diǎn)之間最可靠的路徑。

7-7設(shè)G=(V，E)為加權(quán)有向圖，權(quán)函數(shù)為w：E→{0，1，…，W}，其中W是一非負(fù)整數(shù)。修改Dijkstra算法，使得對(duì)于給定的源點(diǎn)s，計(jì)算最短路徑的運(yùn)行時(shí)間為O(WV+E)。

7-8單源點(diǎn)最短路徑問題的Gabow定標(biāo)算法。定標(biāo)算法按照以下步驟求解問題。初始時(shí)，只考慮每個(gè)相關(guān)輸入值(如邊的權(quán)值)的最高位，然后通過檢查兩個(gè)最高位對(duì)初始解進(jìn)行求精，像這樣逐步檢查更多的最高位，同時(shí)每次都對(duì)前次的解進(jìn)行求精，直到檢查完所有位且計(jì)算出正確解為止。

在這個(gè)問題中，考察一種通過定標(biāo)邊權(quán)值計(jì)算單源點(diǎn)最短路徑的算法。給定有向圖G=(V，E)，其中邊上權(quán)值w為非負(fù)整數(shù)。設(shè)W=max(u,v)∈E{w(u,v)}。目標(biāo)是研制一種運(yùn)行時(shí)間為O(ElgW)的算法。假設(shè)所有頂點(diǎn)由源點(diǎn)可達(dá)。算法用二進(jìn)制表示邊的權(quán)值。并從最高位到最低位每次檢查一位。設(shè)k=［lg(W+1)］為W的以二進(jìn)制表示的位數(shù)，對(duì)于i=1，2，…，k，令wi(u，v)=［w(u，v)/2k－i］，即wi(u，v)是取w(u，v)的二進(jìn)制表示的i個(gè)高位而得。因此，對(duì)于所有(u，v)∈E，wk(u，v)=w(u，v)。例如，如果k=5，w(u，v)=25，它的二進(jìn)制表示為〈11001〉，那么w3(u，v)=〈110〉=6；如果對(duì)于k=5，w(u，v)=4，它的二進(jìn)制表示為〈00100〉，那么w3(u，v)=〈001〉=1。定義δi(u，v)為從u到v且使用權(quán)函數(shù)wi的最短路徑權(quán)值。因此，對(duì)于所有u，v∈V，δk(u，v)=δ(u，v)。對(duì)于給定的源點(diǎn)s，定標(biāo)算法首先對(duì)于所有v∈V計(jì)算出最短路徑的權(quán)值δ1(s，v)，然后對(duì)于所有v∈V計(jì)算出最短路徑的權(quán)值δ2(s，v)，繼續(xù)這一過程，直到對(duì)于所有v∈V計(jì)算出最短路徑的權(quán)值δk(s，v)。假設(shè)|E|≥|V|－1，則由δi－1計(jì)算出δi所需的運(yùn)行時(shí)間為O(E)。因此，整個(gè)算法的運(yùn)行時(shí)間為O(kE)=(ElgW)。

(1)假設(shè)對(duì)于所有v∈V的頂點(diǎn)，有δ(s，v)≤|E|。證明可以用O(E)時(shí)間計(jì)算出