計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第10章 單源最短路徑

1第10

章

單源最短路徑單源最短路徑問題簡介

2Dijkstra算法

3Ballman-Ford算法 1421.單源最短路徑問題簡介問題定義：在給定的加權(quán)有向圖G(V,E)中，取一頂點(diǎn)s為源點(diǎn)，計(jì)算從源點(diǎn)s到其他每個(gè)點(diǎn)v的最短路徑p(s,v)，v

V，以及它的加權(quán)長度。最短路徑的長度記為

(s,v)。主要算法：

Dijkstra算法和Ballman-Ford算法都采用貪心法策略，包括初始化和循環(huán)部分。初始化置d(v)

=

，v

V–{s}，置d(s)

=0。d(v)含義是，到目前為止，能找到的從s到v的路徑中最短的一條長度。循環(huán)部分，每一輪都會有至少一個(gè)新頂點(diǎn)的最短路徑被確定下來。這樣，在n輪之后，所有頂點(diǎn)的最短距離就產(chǎn)生了。（有些學(xué)者把Ballman-Ford算法歸為動態(tài)規(guī)劃。）32.Dijkstra算法Dijkstra算法要求圖G(V,E)中邊的權(quán)值是非負(fù)實(shí)數(shù)。Dijkstra算法與Prim算法幾乎完全一樣。Dijkstra算法構(gòu)造一棵最短路徑樹T，而Prim算法是構(gòu)造MST。Dijkstra算法既適用于有向圖又適用于無向圖。Dijkstra算法簡介

分為兩部分，初始化部分和循環(huán)部分。(1)初始化部分(和Prim算法完全一樣，但d(v)的含義不同):foreachv

V

d(v)

(v)

nil //點(diǎn)v的父親

endford(s)

0這里，d(v)表示從源點(diǎn)s到v的暫時(shí)距離，即目前找到的最短距離。在Prim算法中，d(v)表示的是，點(diǎn)v與當(dāng)前已形成的樹T的最短距離。4Dijkstra算法簡介(繼續(xù)1)(2) 循環(huán)部分：循環(huán)前，樹T是空集。以d(v)為關(guān)鍵字，用優(yōu)先隊(duì)列Q把所有樹外的頂點(diǎn)組織起來。一共循環(huán)n次，每次循環(huán)做兩件事：(2,1)

找出當(dāng)前樹T以外的頂點(diǎn)中有最小d(u)的頂點(diǎn)u。

和Prim算法完全一樣，如果

(u)=h，那么，Dijkstra算法把邊

(h,u)加到樹T中，并且把u從Q中刪除，修復(fù)Q。因?yàn)閐(s)=0

<

，循環(huán)第一輪必定選取源點(diǎn)s。因?yàn)?/p>

(s)=nil，第一輪只把點(diǎn)s加到T里，沒有邊加入T。(2,2)

逐個(gè)檢查點(diǎn)u的還在樹外的每個(gè)鄰居v，即v

Adj(u)，v

Q。點(diǎn)u成了樹中的點(diǎn)，為鄰居v提供一條新路徑，長為d(u)+w(u,v)。如果d(u)+w(u,v)<d(v)，則d(v)更新為d(v)

d(u)+w(u,v)。(偽碼見下頁)5Dijkstra算法簡介(繼續(xù)2)foreachv

Adj(u)

ifv

Q

and

d(u)+w(u,v)<d(v)

then

d(v)

d(u)+w(u,v)

(v)

u

endifendfor這一部分的偽碼幾乎和Prim相同。只要作如下改動就變成Prim算法了。把d(u)

+w(u,v)<d(v)

改為

w(u,v)<d(v),和把d(v)

d(u)

+w(u,v) 改為

d(v)

w(u,v)，也就是把”

d(u)

+“去掉，

就變成Prim算法了。

(完整的Dijkstra算法的偽碼見下頁)6SSSP-Dijkstra(G(V,E),s) //SSSP–SingleSourceShortestPath1 for

eachv

V2 d(v)

3

(v)

nil4 endford(s)

06 V(A)

//A是樹T的邊集合，V(A)是與A中邊關(guān)聯(lián)的頂點(diǎn)集合7 A

//初始，樹T的邊集合為空8 Q

V

//所有樹外的頂點(diǎn)組織為Q9 while

Q

10 u

Extract-Min(Q) //從Q中剝離最小d(u)，修復(fù)Q11 A

A

{(

(u),u)} //如

(u)=nil，A不變12 V(A)

V(A)

{u}13 foreachv

Adj(u)14

if

v

Q

andd(u)+w(u,v)<d(v)

15

then

d(v)

d(u)+w(u,v)16

(v)

u17

endif

endforendwhile18 returnT(V(A),A)

//最短路徑樹19 End把14行和15行中的d(u)+去掉就變成Prim算法了。7例10.1

用Dijkstra算法找出下圖中以頂點(diǎn)s為源點(diǎn)的最短路徑樹。1243852abscde131085解：d(a)=

(a)=nild(c)=

(c)=nil1243852abscde131085d(b)=

(b)=nild(d)=

(d)=nild(e)=

(e)=nild(s)=0

(s)=nil(a)初始化，源點(diǎn)是頂點(diǎn)ss1243852abcde131085d(a)=12

(a)=sd(c)=

(c)=nild(b)=4

(b)=sd(d)=

(d)=nild(e)=

(e)=nild(s)=0

(s)=nil(b)頂點(diǎn)

s被選中，更新頂點(diǎn)a，b8d(a)=9

(a)=bd(c)=14

(c)=b1243852abscde131085d(b)=4

(b)=sd(d)=12

(d)=bd(e)=

(e)=nild(s)=0

(s)=nil(c)頂點(diǎn)b被選中，更新頂點(diǎn)a，c，ds1243852abcde131085d(a)=9

(a)=bd(c)=12

(c)=a

d(b)=4

(b)=sd(d)=12

(d)=bd(e)=

(e)=nild(s)=0

(s)=nil(d)頂點(diǎn)a被選中，更新頂點(diǎn)cd(a)=9

(a)=bd(c)=12

(c)=a1243852abscde131085d(b)=4

(b)=sd(d)=12

(d)=bd(e)=17

(e)=cd(s)=0

(s)=nil(e)頂點(diǎn)c被選中，更新頂點(diǎn)es1243852abcde131085d(a)=9

(a)=bd(c)=12

(c)=a

d(b)=4

(b)=sd(d)=12

(d)=bd(e)=14

(e)=dd(s)=0

(s)=nil(f)頂點(diǎn)d被選中，更新頂點(diǎn)e9d(a)=9

(a)=bd(c)=12

(c)=a1243852abscde131085d(b)=4

(b)=sd(d)=12

(d)=bd(e)=14

(e)=dd(s)=0

(s)=nil(g)頂點(diǎn)e被選中，不需更新頂點(diǎn)s4382abcde5d(a)=12

(a)=sd(c)=12

(c)=a

d(b)=4

(b)=sd(d)=12

(d)=bd(e)=14

(e)=dd(s)=0

(s)=nil(h)Dijkstra

算法產(chǎn)生的最短路徑樹10Dijkstra算法正確性證明假設(shè)源點(diǎn)s有路徑到達(dá)圖中每一個(gè)點(diǎn)。顯然算法一定輸出一棵樹。只需證明以下命題：初始化后，每一輪while循環(huán)中，點(diǎn)u被選中并連到樹T上去時(shí)，從s到u的路徑就是最短路徑，其長是d(u)=

(s,u)。我們用歸納法證明。歸納基礎(chǔ)：因?yàn)閐(s)=0<

，第一個(gè)被選中的點(diǎn)必定是源點(diǎn)s。因?yàn)閳D中所有權(quán)值都大于等于零，顯然d(s)=

(s,s)=0正確。歸納步驟：假沒k次循環(huán)后，算法已正確地選取了k個(gè)頂點(diǎn)(1

k

n-1)，使得樹中從s到這k個(gè)頂點(diǎn)的任一個(gè)點(diǎn)z的路徑就是圖G中從s到z的一條最短路徑，長為d(z)=

(s,z)?，F(xiàn)在證明算法選取的第k+1個(gè)頂點(diǎn)u也是正確的。(接下頁)11歸納步驟(繼續(xù)1)設(shè)

(u)=h，則有d(u)=d(h)

+w(h,u)。由歸納假設(shè)，d(h)是從源點(diǎn)s到點(diǎn)

h的路徑長度，并且有d(h)=

(s,h)。所以，d(u)就是沿著樹中從源點(diǎn)s到點(diǎn)h，再到點(diǎn)u的路徑的長度。當(dāng)我們把邊(h,u)加到樹中，d(u)就是樹中從源點(diǎn)s到點(diǎn)u的路徑的長度。所以，我們只需證明，這條路徑是圖G中從s到u的最短路徑。我們用反證法，并為此假設(shè)圖中有一條比d(u)還短的路徑p(s,u)，w(p(s,u))<d(u)。我們將由此導(dǎo)出矛盾。我們?yōu)轫旤c(diǎn)集合V定義一個(gè)割，C={S,V-S}，其中S是當(dāng)前已選入樹T中的k個(gè)點(diǎn)，而V-S是樹外的n-k個(gè)點(diǎn)，包括點(diǎn)u。因?yàn)樵袋c(diǎn)s和頂點(diǎn)u分屬割的兩邊，路徑p(s,u)含有至少一條交叉邊。設(shè)(x,y)是路徑p(s,u)上第一條交叉邊，x

S，y

V-S。如下圖(10.2)所示，我們可以把路徑p(s,u)分為三段:（接下頁）12第1段p1，w(p1)=d(x)第2段p2，w(p2)=w(x,y)第3段p3，是從y到u的一

條路徑，w(p3)

0sxySp1p3d(y)

d(u)

d(y)V–Su割C=（S，V-S）w(x,y)p2因?yàn)閣(p1)+w(p2)=d(x)+w(x,y)正是在先前x被選中時(shí)用于更新d(y)的，所以必有d(y)

d(x)+w(x,y)。否則，d(y)在那個(gè)時(shí)刻應(yīng)該更新而沒有更新，違反了算法。所以，我們必有如下關(guān)系： d(y)

w(p1)+

w(p2)

w(p(s,u))<d(u)，即d(y)

<d(u)。這與算法矛盾，因?yàn)樗惴ㄔ谶x取點(diǎn)u時(shí)，必有d(u)

d(y)。所以，d(u)是圖中從s到u的最短路徑長度，歸納成功。

d(x)

歸納步驟(繼續(xù)2)13Dijkstra算法的復(fù)雜度顯然與Prim算法的復(fù)雜度相同，總結(jié)如下：用數(shù)組作為Q來存儲d(v)，v

V，復(fù)雜度為O(n2)。用最小堆作為Q來存儲d(v)，v

V，復(fù)雜度為O(mlgn)。用裴波拉契堆作為Q來存儲d(v)，v

V，復(fù)雜度為O(nlgn

+m)。14Bellman-Ford

算法簡介由三部分組成，分述如下。初始化: 與Dijkstra算法的初始化完全相同，組織為一個(gè)子程序如下：Initialize-Single-Source(G(V,E),s)foreachv

V

d(v)

(v)

nilendford(s)

0End3.Bellman-Ford算法15Bellman-Ford

算法簡介

(繼續(xù)1)循環(huán)部分: 做n-1輪循環(huán)。每輪只做一件事，即對每條邊(u,v)進(jìn)行一次松弛(relax)操作如下：Relax(u,v)if

d(u)+w(u,v)<d(v)

then

d(v)

d(u)+w(u,v)

(v)

uendifEnd其實(shí)，這就是Dilkstra算法的更新操作。不同的是，Dilkstra算法每一輪只對u的鄰居

v

Adj(u)進(jìn)行更新。而Bellman-Ford算法對每條邊都要進(jìn)行松弛操作。所以，我們稱一輪循環(huán)為一輪松弛遍歷，遍歷時(shí)，邊的順序可任意，只要每條邊都被松弛操作即可。16Bellman-Ford

算法簡介

(繼續(xù)2)檢查部分。在循環(huán)部分完成后，需要檢測有沒有源點(diǎn)可達(dá)的負(fù)回路。檢測很簡單，就是再做一次松馳遍歷。在遍歷中，如果有某頂點(diǎn)v的d(v)得到更新，變得更小，則說明有源點(diǎn)可達(dá)負(fù)回路。這時(shí)，算法報(bào)告有負(fù)回路，并取消所有計(jì)算。反之，任何d(v)都沒有更新，算法成功結(jié)束。這時(shí)，每個(gè)d(v)即是從源點(diǎn)s到頂點(diǎn)v的最短路徑的距離，其對應(yīng)的最短路徑則可以通過父親指針而找到。(偽碼見下頁)17Bellman-Ford

(G(V,E),s)Initialize-Single-Source(G(V,E),s) //初始化for

i

1to

n-1 //n=|V|,松弛遍歷 foreachedge(u,v)

E Relax(u,v) endforendforforeachedge(u,v)

E //開始檢測負(fù)回路 if

d(u)

+w(u,v)<d(v)

thenreturn

false //有源點(diǎn)可達(dá)負(fù)回路

endifendforA

{(

(v),v)|v≠s,v

V} //最短路徑樹中邊的集合constructT(V,A) //構(gòu)造最短路徑樹return

(T(V,A))，End18例：

用Bellman-Ford算法找出下圖中以頂點(diǎn)s為源點(diǎn)的最短路徑樹。

-2acebd-1-57486s5-3解：d(b)=

(b)=nild(s)=0

(s)=nilacebd-2-1-57486s5-3(a)初始狀態(tài)，源點(diǎn)是頂點(diǎn)sd(a)=

(a)=nild(e)=

(e)=nild(d)=

(d)=nild(c)=

(c)=nild(s)=0

(s)=nilacebd-2-1-57486s5-3(b)第1輪松馳遍歷后狀態(tài)。遍歷順序?yàn)?a,b)，(b,e)，(b,d)，(s,a)，(s,c)，(c,a)，(c,b)，(c,d)，(d,e)。d(a)=1

(a)=cd(b)=3

(b)=cd(e)=12

(e)=dd(d)=5

(d)=cd(c)=-3

(c)=s19(c)第2輪松馳遍歷后狀態(tài)。遍歷順序?yàn)?s,a)，(s,c)，(c,b)，(c,d)，(d,e)，(c,a)，(b,d)，(b,e)，(a,b)。acebd-2-1-57486s5-3d(a)=1

(a)=cd(b)=-1

(b)=ad(e)=2

(e)=bd(d)=-2

(d)=bd(c)=-3

(c)=sd(s)=0

(s)=nilacebd-2-1-57486s5-3(d)第3輪松馳遍歷后狀態(tài)。遍歷順序?yàn)?s,a)，(s,c)，(c,b)，(c,d)，(d,e)，(c,a)，(b,d)，(b,e)，(a,b)。d(b)=-1

(b)=ad(e)=-2

(e)=bd(d)=-6

(d)=bd(c)=-3

(c)=sd(s)=0

(s)=nild(a)=1

(a)=c20(e)第4輪松馳遍歷后狀態(tài)。遍歷順序?yàn)?s,a)，(s,c)，(c,b)，(c,d)，(d,e)，(c,a)，(b,d)，(b,e)，(a,b)。acebd-2-1-57486s5-3d(a)=1

(a)=cd(b)=-1

(b)=ad(e)=-2

(e)=bd(d)=-6

(d)=bd(c)=-3

(c)=sd(s)=0

(s)=nilacebd-2-1-57486s5-3(f)第5輪松馳遍歷后狀態(tài)。遍歷順序?yàn)?/p>

(s,a)，(s,c)，(c,b)，(c,d)，(d,e)，(c,a)，(b,d)，(b,e)，(a,b)。d(b)=-1

(b)=ad(e)=-2

(e)=bd(d)=-6

(d)=bd(c)=-3

(c)=sd(s)=0

(s)=nild(a)=1

(a)=cacebd-2-1-54s-3(g)Bellman-Ford算法產(chǎn)生的最短路徑樹d(a)=1

(a)=cd(b)=-1

(b)=ad(c)=-3

(c)=sd(s)=0

(s)=nild(d)=-6

(d)=bd(e)=-2

(e)=b21Bellman-Ford算法正確性證明正確性證明包括兩部分。第一部分證明在圖G(V,E)不含源點(diǎn)可達(dá)負(fù)回路的情況下，Bellman-Ford算法正確地算出各頂點(diǎn)的最短路徑。第二部分證明在G(V,E)含有源點(diǎn)可達(dá)負(fù)回路的情況下，Bellman-Ford算法正確地檢測出負(fù)回路并報(bào)告。我們通過兩個(gè)定理來證明。注意，只有所有邊的權(quán)值都非負(fù)時(shí)，Bellman-Ford算法才能用于無向圖。這是因?yàn)椋绻岩粭l無向邊(u,v)換成一對有向邊(u,v)和(v,u)的話，它們形成兩條邊的負(fù)回路。22Bellman-Ford算法正確性證明（繼續(xù)1）從源點(diǎn)s到頂點(diǎn)v的最短路徑可能不止一條，其中必有一條路徑p(s,v)，它不僅有最短的加權(quán)距離，w(p(s,v))=

(s,v)，而且，它的不加權(quán)距離，即它含有的邊的個(gè)數(shù)，|p(s,v)|，在所有最短路徑中也最小。定義10.1設(shè)v

V是有向圖G(V,E)中一頂點(diǎn)，從源點(diǎn)s到頂點(diǎn)v的最小最短距離定義如下： D(s,v)=min{|p(s,v)||滿足w(p(s,v))=

(s,v)的路徑p(s,v)}。滿足|p(s,v)|=D(s,v)和w(p(s,v))=

(s,v)的路徑p(s,v)稱為從s到v的最小最短路徑。由定義10.1，如果D(s,v)=k，那么，源點(diǎn)s到頂點(diǎn)v的所有加權(quán)的最短路徑中，有一條含有k條邊，而其余的加權(quán)的最短路徑至少含有k條邊或者更多。顯然，最小最短距離不會超過n-1，D(s,v)

n-1。(接下頁)23Bellman-Ford算法正確性證明（繼續(xù)2）定理10.1如果G(V,E)不含s可達(dá)的負(fù)回路，那么在算法進(jìn)行了n-1輪松弛遍歷后，圖G中從源點(diǎn)s到頂點(diǎn)v的最短距離是d(v)，即

(s,v)=d(v)。(假定從s到v有通路，否則d(v)=

。)證明：我們先有以下兩點(diǎn)觀察：因?yàn)闆]有負(fù)回路，s到v的所有最短路徑中必有一條簡單路徑。因?yàn)閐(v)值只減不增，一旦有d(v)=

(s,v)，d(v)便不會再變。我們用歸納法證明下面的命題。我們對變量k進(jìn)行歸納證明。命題：如果D(s,v)=k，那么在k輪松弛遍歷后，d(v)=

(s,v)。歸納基礎(chǔ)：當(dāng)k=0時(shí)，源點(diǎn)s的距離d(s)=0。因?yàn)闆]有負(fù)回路，

(s,s)=d(s)=0。從s到s路徑不含邊，D(s,s)=0，所以命題正確。(接下頁)24Bellman-Ford算法正確性證明（繼續(xù)3）定理10.1證明，命題證明（繼續(xù)）歸納步驟：假設(shè)在k-1輪松弛遍歷后(k

1)，命題成立。也就是，任何點(diǎn)v

(v

V)，如果D(s,v)

k-1，那么從s到v的最短距離有等式d(v)=

(s,v)。我們證明在第

k輪松弛遍歷后，命題也成立。假設(shè)D(s,v)=k，從s到v的最短路徑是p(s,v)=<s,v1,v2,…,vk-1,v>，w(p(s,v))=

(s,v)。我們斷言，它的子路徑p(s,vk-1)=<s,v1,v2,…,vk-1>一定是s到vk-1的最短路徑，即

(s,vk-1)=w(p(s,vk-1))。這是因?yàn)?，否則的話，s到vk-1有權(quán)值更小的路徑p*

(s,vk-1)。那么沿著p*

(s,vk-1)，從s到vk-1后，再到v就是一條比w(p(s,v))權(quán)值更小的從s到v的路徑。這與w(p(s,v))=

(s,v)矛盾。(接下頁)25Bellman-Ford算法正確性證明（繼續(xù)4）定理10.1證明，命題證明（繼續(xù)1）因?yàn)閜(s,vk-1)有k-1條邊，又是最短路徑，所以

D(s,vk-1)

k-1。那么，根據(jù)歸納假設(shè)，必有d(vk-1)=

(s,vk-1)=w(p(s,vk-1))。所以，當(dāng)?shù)趉輪松弛遍歷對邊(vk-1,v)進(jìn)行松弛操作時(shí)，如果此時(shí)有d(v)>d(vk-1)+w(vk-1,v)，則必定被更新為:d(v)=d(vk-1)+w(vk-1,v)=w(p(s,vk-1))+w(vk-1,v)=w(p(s,v))=

(s,v)，

(v)=vk-1。歸納成功。否則，d(v)

d(vk-1)