計算機算法基礎(chǔ) 第2版 習題及答案 第10章

PAGE16第10章 單源最短路徑以圖10-1為例，用Dijkstra算法找出下面無向圖中以頂點s為源點的最短路徑樹。33810742abscde4158411解：和書中圖10-1類似，下圖(a)顯示各點v的d(v)和p(v)初始值。圖(b)-圖(g)逐步顯示每一次循環(huán)后，這棵最短路徑樹增長的情況及被更新各點v的d(v)和p(v)值。樹中各點和邊用粗線表示，有父子關(guān)系的邊加上了方向，從父親指向兒子，這不表示原來圖是有向圖，而是表示最短路徑的取向。圖(h)顯示了算法結(jié)束后的最短路徑樹及源點s到各點的距離。10107842abscd4158411d(a)=(a)=nild(c)=(c)=nild(b)=(b)=nild(d)=(d)=nild(s)=0(s)=nil(a)初始化3ed(e)=(e)=nil107842abscde4158411d(a)=10(a)=sd(c)=15(c)=sd(b)=7(b)=sd(d)=(d)=nild(s)=0(s)=nil(b)頂點s被選中，更新a，b，cd(e)=(e)=nil310107842abscde4158411d(a)=10(a)=sd(c)=15(c)=sd(b)=7(b)=sd(d)=15(d)=bd(s)=0(s)=nil(c)頂點b被選中，更新d，ed(e)=18(e)=b3107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(d)頂點a被選中，更新c，dd(e)=18(e)=b310107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(e)頂點c被選中，更新ed(e)=17(e)=c3107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(f)頂點d被選中，更新ed(e)=16(e)=d310107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(g)頂點e被選中，無更新點d(e)=16(e)=d31072abscde4d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(h)算法產(chǎn)生的最短路徑樹d(e)=16(e)=d3以圖10-3為例，用Bellman-Ford算法找出下面有向圖中以頂點s為源點的最小最短路徑樹。每輪松弛遍歷所用的邊的順序請按字母順序確定，即(a,b)，(a,c)，(a,e)，(b,c)，(b,d)，(c,d)，(c,e)，(d,e)，(s,a)，(s,b)，(s,d)。-3-3-1105-24abscde978-2-3解：和書中圖10-3類似，下圖(a)顯示各點v的d(v)和p(v)初始值。圖(b)-圖(c)顯示了前2輪松弛遍歷的結(jié)果。有父子關(guān)系的邊用粗線表示。因為從第3輪開始，松弛遍歷不產(chǎn)生任何更新，所以省去3輪的顯示。圖(d)顯示算法結(jié)束后的最短路徑樹及源點s到各點的距離。(a)(a)初始狀態(tài)，源點是頂點sd(a)=(a)=nild(c)=(c)=nild(e)=(e)=nild(d)=(d)=nild(b)=(b)=nild(s)=0(s)=nil-3-1105-24abscde978-2-3(b)第1輪松弛遍歷后各點的暫時距離d(a)=10(a)=sd(c)=(c)=nild(e)=(e)=nild(d)=-3(d)=sd(b)=5(b)=sd(s)=0(s)=nil-3-1105-24abscde978-2-3(c)(c)第2輪松弛遍歷后各點的暫時距離d(a)=10(a)=sd(c)=7(c)=ad(e)=1(c)=dd(d)=-3(d)=sd(b)=5(b)=sd(s)=0(s)=nil-3-1105-24abscde978-2-3(d)算法產(chǎn)生的最短路徑樹d(a)=10(a)=sd(b)=7(b)=ad(e)=1(c)=dd(d)=-3(d)=sd(c)=5(c)=sd(s)=0(s)=nil-31054abscde-3假設(shè)G=(V,E)是一個加權(quán)有向圖。圖中的每個頂點代表一個通訊網(wǎng)絡(luò)的結(jié)點，而邊(u,v)?E的權(quán)值r(u,v)則表示u和v兩點間信道的可靠性，其范圍是區(qū)間[0,1]中實數(shù)，0￡r(u,v)￡1。我們把r(u,v)理解為u和v兩點間信道正常工作(不出故障)的概率，并假定每條邊的這個可靠性與其他邊的可靠性是獨立無關(guān)的。請設(shè)計一個復(fù)雜度好的算法找到一條從頂點s到頂點t的最可靠路徑。解：我們可以把Dilkstra算法稍加修改后直接解出這個問題，也可以把這個問題先轉(zhuǎn)化為一個最短路徑問題，然后用Dijkstra算法解出。這兩個算法都算出從s到每一個其他頂點的最可靠路徑,當然也包括頂點t，也就是算出以s為源點的最可靠路徑樹。我們知道，如果p(s,v)是一條從s到頂點v的路徑，那么這條路徑的可靠性，記為R(p(s,v))，是路徑上所有邊的可靠性乘積：R(p(s,v))=(x,y)∈p(s,v)r(x,y)。方法一:對Dijkstra算法稍做修改后算法如下：SS-Most-Reliable-Path(G(V,E),s)foreachv?V //初始化，沒有路徑到v，可靠性為0 r(v)?0 //目前找到的最可靠路徑的可靠性，初始為0 p(v)?nilendforr(s)?1 //從源點到源點，始終是可靠的V(A)? //與邊的集合A關(guān)聯(lián)的頂點空集，初始為空A? //初始，邊的集合是空集constructT(V(A),A)Q?V //一開始，所有點都在樹外whileQ1 u?Extract-Max(Q) //找出有最大r(u)值的頂點u A?A{(p(u),u)} V(A)V(A){u} foreachv?Adj(u) //更新頂點u的鄰居 ifr(u)′r(u,v)>r(v) //如果經(jīng)過頂點u的路徑更可靠，更新r(v) then r(v)?r(u)′r(u,v) p(v)?u endif endforendwhilereturnT(V(A),A) //輸出最可靠路徑樹End這個算法的正確性及復(fù)雜度可以像證明Dijkstra算法那樣證明，這里略去。方法二:我們先把圖G轉(zhuǎn)換為新圖G’(V’,E’)使得V’=V，E’=E。兩個圖的區(qū)別在于邊的權(quán)值。對新圖G’(V’,E’)中邊(u,v)?E’，我們賦以權(quán)值w(u,v)=-lgr(u,v)。因為0￡r(u,v)￡1，我們有0￡-lgr(u,v)￡￥。這樣一來，在圖G’中的路徑p(s,t)的加權(quán)長度為：w(p(s,t))==-lg=-lgR(p(s,v))。所以，在G’中的最短路徑在G中就是一條最可靠路徑，反之亦然。因此，G中以s為源點的一棵最可靠路徑樹也就是G’中一棵以s為源點的最短路徑樹，而后者可以用Dijkstra算法解出。(最寬路徑問題)讓我們重溫一下在第9章習題12中我們介紹的最寬路徑問題。在加權(quán)連通圖G(V,E)的一條路徑上權(quán)值最小的一條邊稱為這條路徑的瓶頸，而這條路徑的寬度定義為它的一條瓶頸邊的權(quán)值。圖G中從頂點u到頂點v的所有路徑中寬度最大的一條路徑稱為從u到v的最寬路徑。當然，這個定義也適用于有向圖。在第9章習題12中我們證明了G的最大支撐樹T中任意兩點之間的路徑都是G=(V,E)中這兩點間的最寬路徑?？墒?，用最大支撐樹T來找最寬路徑的方法不能直接應(yīng)用到有向圖。請把Dijkstra算法修改為一個可以為有向圖計算從一源點s到其他各點的最寬路徑樹，稱為單源最寬路徑樹。你需要證明算法的正確性，特別要證明，既使圖中有源點可達負回路，算法也是正確的。解：修改后的算法如下。SS-Widest-Path(G(V,E),s)foreachv?V d(v)?- //初始化，沒有路徑到v，寬度d(v)為- p(v)?nilendford(s)? //從源點到源點，寬度d(s)為無窮大V(A)A //一開始，最寬路徑樹沒有邊constructT(V(A),A)Q?V //所有點vV以d(v)為關(guān)鍵字，組織在優(yōu)先隊列Q中whileQ1 u?Extract-Max(Q) //找出有最大d(u)值的頂點u，第一輪必定是s A?A{(p(u),u)} V(A)V(A){u} foreachv?Adj(u) //更新頂點u的鄰居 ifmin{d(u),w(u,v)}>d(v) //如果經(jīng)過頂點u的路徑更寬，更新d(v) then d(v)?min{d(u),w(u,v)} p(v)?u endif endforendwhilereturnT(V(A),A)End正確性證明：我用用歸納法證明。在證明過程中，我們允許權(quán)值為任何實數(shù)，所以算法允許負數(shù)和負回路。一個有用的觀察是，如果從源點s到頂點v的路徑上經(jīng)過一個回路，那么，不論是正回路還是負回路，把這個回路從路徑上摘去后所得到的路徑只會更寬不會更窄。所以，既使有負回路，一定有一條從頂點s到頂點v的最寬路徑是簡單路徑。下面我們用歸納法證明以下命題：算法在初始化之后第10行開始的循環(huán)中，每次循環(huán)確定一條最寬路徑，即從源點s到選中的頂點u的最寬路徑，其寬度為d(u)。歸納基礎(chǔ)：第1次循環(huán)一定選中源點s。因為從源點s到s不需經(jīng)過任何邊，d(s)=顯然是正確的。歸納步驟：假設(shè)經(jīng)過k次循環(huán)后(1k<n)，從源點s到k個點的最寬路徑都已正確地確定。而且，從源點s到這k個點中任一頂點z的最寬路徑的寬度是d(z)。現(xiàn)在證明，如果第k+1次循環(huán)中選中的是頂點u，那么從源點s到(u)再到u是一條從源點s到u的最寬路徑，其寬度為d(u)。為了用反證法證明，我們假設(shè)這條路徑不是最寬的，最寬路徑是p(s,u)，其寬度是d(p(s,u))>d(u)，我們將導出矛盾。讓我們定義一個割，C={S,V-S}，其中S是前面k次循環(huán)得到的樹中的k個點，而V-S是樹外的n-k個點。這條比d(u)還寬的路徑p(s,u)含有至少一條交叉邊。設(shè)(x,y)是路徑p(s,u)上第一條交叉邊。如下圖所示，我們可以把p(s,u)分為三段:第1段是樹里從s到x的路徑，p1，根據(jù)假設(shè)，它的寬度為d(p1)=d(x)。第2段p2是邊(x,y)，其寬度為w(x,y)。 第3段是y到u的路徑，p3，它的寬度為d(p3)。ssxySp1p3d(y)d(u)d(y)V-Su割C=(S,V-S)p2=(x,y)樹中k個點d(x)由定義，路徑p(s,u)的寬度為d(p(s,u))=min{d(p1)，w(x,y)，d(p3)}=min{d(x)，w(x,y)，d(p3)}由反證假設(shè)，d(p(s,u))>d(u)，所以有min{d(x)，w(x,y)，d(p3)}>d(u)因為min{d(x)，w(x,y)}min{d(x)，w(x,y)，d(p3)}，我們有min{d(x)，w(x,y)}>d(u)因為頂點x是早先被選入樹中的k個點之一，而min{d(x)，w(x,y)}恰恰是在頂點x被選中時向鄰居y提供的路徑的寬度，也就是用來更新d(y)的值。所以，必有d(y)min{d(x)，w(x,y)}。否則的話，頂點y在那個時刻應(yīng)該更新而沒有更新，違反了算法。所以，我們必有如下關(guān)系：d(y)min{d(x)，w(x,y)}>d[u]，即d(y)>d(u)。這與算法矛盾，因為算法在選取第k+1個點u時，它的d(u)值是所有樹以外的頂點中最大的，包括頂點y在內(nèi)。這個矛盾說明不存在比d(u)還寬的路徑，歸納成功，命題正確。命題正確直接證明了算法的正確。一個傳感器網(wǎng)絡(luò)(sensornetwork)可以用一個加權(quán)有向圖G(V,E)來建模。圖中的每個頂點代表一個傳感器(sensor)，而每條邊(u,v)表示從傳感器u可以用無線電頻道送信息給傳感器v。我們假定每個傳感器u都是用電池來工作的。每當邊(u,v)使用一次，即傳感器u向傳感器v傳輸一個單位信息，傳感器u需要消耗能量w(u,v)。如果傳輸前傳感器u的能量是P(u)，那么傳輸后它的剩余能量就是P(u)-w(u,v)。接收信息的傳感器v消耗的能量可忽略不計。當傳感器u的能量少于某個值時就不能工作而使整個網(wǎng)絡(luò)癱瘓?，F(xiàn)在，我們希望在網(wǎng)絡(luò)中找一條從頂點s到頂點t的路徑來傳輸一個單位信息。傳輸前每個傳感器u的能量已知為P(u)，傳輸后，路徑上各點的能量會得到不同的減少。其中剩余能量最少的點威脅著網(wǎng)絡(luò)的安全。這個有最少剩余能量的頂點稱為是這條路徑的瓶頸點。請設(shè)計一個復(fù)雜度好的算法找到一條從頂點s到頂點t的路徑使得傳輸后這條路徑的瓶頸點的剩余能量最大。(提示：用第4題結(jié)果。)解:我們從加權(quán)有向圖G(V,E)來構(gòu)造一個新的加權(quán)有向圖G’(V’,E’)。其中V’=V,E’=E。因為當邊(u,v)使用后，傳感器u的能量變?yōu)镻(u)-w(u,v)，我們用w’(u’,v’)=P(u)-w(u,v)表示使用邊(u,v)后傳感器u的剩余能量。這樣一來，G中一條路徑的瓶頸點就變成G’中對應(yīng)路徑的瓶頸邊。因此，在G中找一條從頂點s到頂點t有最大瓶頸點剩余能量的路徑就等價于找一條G’中從頂點s’到頂點t’的最寬路徑。算法的偽碼如下：Max-Min-Path(G(V,E)) V’?V //頂點v’vE’?E //(u’,v’)(u,v)foreachedge(u,v)?E //給G’(V’,E’)中邊賦權(quán)值 w’(u’,v’)?P(u)-w(u,v)SS-Widest-Path(G’(V’,E’),s’) //調(diào)用第4題算法在G’中找出以s’為源的最寬路徑樹p(s,t)?p(s’,t’) //G’中從頂點s’到頂點t’的最寬路徑就是解returnp(s,t)End假設(shè)G=(V,E)是一個加權(quán)有向圖并且從源點s為出發(fā)點的邊中可能有負數(shù)的權(quán)值，但其他邊的權(quán)值沒有負數(shù)，并且圖中沒有負回路。證明Dijkstra算法仍可以正確解決單源最短路徑問題。解：我們?nèi)杂脷w納法證明以下命題：當頂點u被選中而連到樹上去時，d(u)值就是從源點s到頂點u的最短矩離，對應(yīng)的最短路徑是從源點s到u的父親頂點p(u)，再到u。歸納基礎(chǔ)：從算法可知，因為d(s)=0<￥，第一個被選中的點必定是源點s。因為圖中沒有負回路，沒有一條從s到s的路徑會有小于零的長度，顯然這是個正確的距離。歸納步驟：假沒算法已經(jīng)正確地選取了k個頂點在樹中(1￡k<n)，即樹中從源點s到這k個頂點的任一個點z的路徑都是從源點s到該點的一條最短路徑，長度為d(z)?，F(xiàn)在證明算法選取的第k+1個頂點u也是正確的，也就是要證明d(u)一定是一條最短路徑的距離。我們用反證法來證明它。假設(shè)圖中還有一條比d(u)還短的路徑p(s,u)，w(p(s,u))<d(u)。我們將由此導出矛盾。首先，因為沒有負回路，我們可以假定路徑p(s,u)是條簡單回路。其次，讓我們定義一個割，C={S,V-S}，其中S是樹中的k個點，而V-S是樹外的n-k個點。這條比d(u)還短的路徑p(s,u)含有至少一條交叉邊。設(shè)(x,y)是從源點s出發(fā)的這條路徑上第一條交叉邊。如下圖所示，我們可以把路徑p(s,u)分為三段:第1段是樹里從s到x的路徑，p1，根據(jù)歸納假設(shè)，它的長度為w(p1)=d(x)。第2段p2是邊(x,y)，其長度為w(x,y)。第3段是y到u的路徑，p3。因為p(s,u)是條簡單回路，p3不經(jīng)過源點s，故有w(p3)30。ssxySp1P3d(y)d(u)￡d(y)V-Su割C=(S,V–S)p2=(x,y)樹中k個點由假設(shè)，w(p(s,u))=w(p1)+w(x,y)+w(p3)<d(u)。因為w(p3)30，我們有w(p1)+w(x,y)<d(u)，也就是w(x)+w(x,y)<d(u)?？墒?，因為頂點x是早先被選入樹中的k個點之一，而d(x)+w(x,y)恰恰是在頂點x被選中時向鄰居y提供的用以更新d(y)的距離。所以，必有d(y)￡d(x)+w(x,y)。否則的話，頂點y在那個時刻應(yīng)該更新而沒有更新，違反了算法。所以，我們必有如下關(guān)系：d(y)￡d(x)+w(x,y)<d(u)，即d(y)<d(u)。這與算法矛盾，因為算法在選取第k+1個點u時，它的d(u)值是所有樹以外的頂點中最小的，包括頂點y在內(nèi)。這個矛盾說明不存在比d(u)還短的路徑，歸納成功。假設(shè)G(V,E)是一個加權(quán)有向圖并且邊的權(quán)值函數(shù)是w:E?{0,1,…,W}，這里W是一個正整數(shù)。請修改Dijkstra算法使之能在O(Wn+m)時間內(nèi)算出以頂點s為源點的最短路徑樹。解: 我們需要設(shè)計一個數(shù)據(jù)結(jié)構(gòu)Q使得Dijkstra算法的每次循環(huán)中以下兩件事情可以做得比較快：u?Extract-Min(Q)，如果d(u)+w(u,v)<d(v)，更新u的鄰居v的d(v)值。我們一共要做n次第一件事，m次第二件事。我們注意到任一條最短路徑最多有(n-1)條邊，其加權(quán)長度一定在區(qū)間[0，(n-1)W]內(nèi)。所以，我們?yōu)槊恳粋€可能的暫時距離的值定義一個集合：L[k]={u|d(u)=k}(0￡k￡(n-1)W)，L[(n-1)W+1]={u|d(u)=￥}。也就是說，所有暫時矩離相同的點放在一個集合中，并用鏈表把它們串起來，一共有(n-1)W+2個集合。頂點u的暫時矩離是d(u)，所以，它所在的集合是L[d(u)]。初始化時，除源點s外的所有點都在集合L[(n-1)W+1]中?，F(xiàn)在來看看我們?nèi)绾蝸碜錾鲜鰞杉?。當我們要做第一件事時，我們就按L[0]，L[1]，L[2]，…順序?qū)ふ业谝粋€非空集合。這第一個非空集合中的頂點都有最短的暫時距離。我們?nèi)稳∫粋€即可。但是，真這樣做，時間會很長。我們注意到，因為每次選中的點的暫時距離是單調(diào)遞增的。如果我們上次是在L[k]中選到一頂點，那么這次我們只需要從L[k]開始尋找，因為L[0]，L[1]，L[2]，…，L[k-1]表必定為空且永遠為空。假設(shè)我們從L[k]開始尋找，如果L[k]非空，那我們只需O(1)時間即可完成第一件事。如果L[k]是空集，那我們就要查看L[k+1]。發(fā)現(xiàn)L[k]是空集并進入L[k+1]需要的時間是O(1)。這種發(fā)現(xiàn)空集的情況總共最多有(n-1)W+1次，所以做第一件事總共需要O(Wn)時間。每次循環(huán)中的第二件事就是更新u的鄰居v的d(v)值。當d(u)+w(u,v)<d(v)時，我們就把v從鏈表L[d(v)]中摘除，然后把它插到鏈表L[k]中，這里k=d(u)+w(u,v)。所以這第二件事只需常數(shù)時間O(1)。因為算法一共需要做n次第一件事，m次第二件事，算法的復(fù)雜度是O(nW+m)。下面是祥細的偽碼。Modified-Dijkstra(G(V,E),s)Initialize-single-source(G,s) //初始化，與原Dijkstra算法同fork0tonW L[k]? //建立鏈表L[k]endforL[0]?{s}L[(n-1)W+1]?V–{s}minset?0 //最小非空集合的號碼V(A)Awhileminset1(n-1)W+1 ifL[minset]1 then u?Extract(L[minset]) //抽取一個頂點 AA{((u),u)} V(A)V(A){u} foreachv?Adj(u) ifd(u)+w(u,v)<d(v) then L[d(v)]?L[d(v)]–{v} d(v)?d(u)+w(u,v) (v)?u L[d(v)]?L[d(v)]è{v} endif endfor elseminset?minset+1 endifendwhilereturnT(V(A),A)End假設(shè)我們需要沿一條長為l公里的公路兩側(cè)布置一些炮兵陣地，使得整個公路都在炮火控制之下。假設(shè)有n個可供選擇的炮兵陣地，順序標以1，2，…，n。因地形的差異，每個陣地可配備的火炮數(shù)量不同，而且只能控制一小段公路。假設(shè)陣地i(1≤i≤n)可以控制從S[i]到E[i]的一段。這里S[i]和E[i]分別是這一小段公路兩端與公路起點的距離，0≤S[i]<E[i]≤l。另外，假定構(gòu)筑陣地i需要費用C[i]>0。下圖是一個n=7的例子。CC[7]=4l=5公里2.3123C[1]=3C[2]=2C[3]=6S[1]=01.20.3C[5]=30.91.851.64C[4]=83.44.43.66C[6]=53.84.17E[1]S[2]E[3]E[6]E[7]E[5]S[5]S[6]S[7]E[2]S[3]S[4]E[4]假定在所有陣地上都布置炮位，整個公路可以復(fù)蓋，但代價太大。我們希望從中找出一部分陣地使得整個公路可以復(fù)蓋，而且總的費用最小。例如，在上面的例子中，我們可選陣地1，3，5，7，總代價是C=C[1]+C[3]+C[5]+C[7]=3+6+3+4=16，可以證明是最好的。請用上例解釋怎樣把這個優(yōu)化問題建模為一個圖的最短路徑問題解出(偽碼不要求)。解: 因為n個陣地順序編號，故有S[1]S[2]…S[n]。我們構(gòu)造一個有向圖，步驟如下：為陣地i建一個頂點vi(1≤i≤n)。如果有S[i]<S[j]≤F[i]<F[j](1i<jn)，則構(gòu)造一條邊(vi,vj)。這就是說，如果兩段公路相交但不互相包含，則有一條邊，從離公路起點近的陣地指向后者。給邊(vi,vj)賦一權(quán)值w(vi,vj)=C[i]。加上一個頂點s。如果S[i]=0(1≤i≤n)，則建一條邊(s,vi)，并賦權(quán)值w(s,vi)=0。這樣的陣地i一定存在，否則不可能復(fù)蓋整個公路。加上一個頂點t。如果F[j]=l(1≤j≤n)，則建一條邊(vj，t)，并賦權(quán)值w(vj，t)=C[j]。這樣的陣地j一定存在，否則不可能復(fù)蓋整個公路。以上面圖形為例，構(gòu)造的有向圖如下：vv1v2v3v6v7v5v4ts04533226633888圖構(gòu)造好之后，圖中的一條從s到t的路徑對應(yīng)一種選擇方案，該路徑的總權(quán)值就是該方案的總費用。所以，找到從s到t的最短路徑也就解決了這個優(yōu)化問題。以上面圖為例，一條最短路徑用粗線標出，它對應(yīng)的解是{1，3，5，7}，總費用為16。因為這個圖無回路，可以用拓撲排序后線性時間解出。算法的主要工作在構(gòu)造這個圖，其復(fù)雜度顯然是O(n2)。假設(shè)有向圖G(V,E)中邊的權(quán)值都是正數(shù)，|V|=n,|E|=m。P(s,t)是圖G(V,E)中從點s到點t的一條最短路徑。我們希望找一條從點s到點t的第二短路徑，也就是說，在所有與P(s,t)不同的簡單路徑中，找一條最短的路徑。這條路徑只要有任何一條邊與P(s,t)不同即可，這條路徑也許和P(s,t)一樣長，也許不存在。請設(shè)計一個O(n3)或更好算法找到這條第二短路徑，或報告不存在，并證明正確性。解： 假設(shè)P(s,t)是圖G(V,E)中從點s到點t的一條最短路徑。我們注意到，如果第二短路徑存在，它不可能包含路徑P(s,t)的所有邊。這是因為，在路徑P(s,t)上加上任何邊的路徑不可能是條簡單路徑。所以，我們的做法是，每次從圖G(V,E)中刪去一條P(s,t)的邊，然后在刪去這條邊的圖中找一條從點s到點t的最短路徑。如果P(s,t)有k條邊，我們需要對k個圖求從點s到點t的最短路徑。那么，最短的一條就是解。偽碼如下。Second-Shortest-Path(G(V,E),P(s,t))dpathforeachedgeeP(s,t) E’E–{e} SSP-Dijkstra(G(V,E’),s) //為每點v計算最短路徑p(s,v)，長為d(v) ifd(t)<d then dd(t) pathp(s,t) //這一步需要構(gòu)造路徑，略去細節(jié) endifendforifd= thenreturn(Nosecondpathatall) elsereturnpath,dEnd因為第5行調(diào)用算法SSP-Dijkstra最多n-1次，如果我們用數(shù)組作為優(yōu)先隊列，上述算法有復(fù)雜度O(n3)。如果我們用斐波那契堆作為優(yōu)先隊列，上述算法有復(fù)雜度O(n2lgn+mn)。假設(shè)有向圖G(V,E)中邊的權(quán)值都是正數(shù)，|V|=n,|E|=m。雖然我們可以用Dijkstra算法得到一棵以源點s為根的最短路徑樹T，但樹T只提供一條從源點s到其它每一個頂點v的最短路徑。有時我們希望知道是否還有一條不同的最短路徑。請設(shè)計一個O(n2)算法，為每個頂點v判斷有幾條不同的從源點s到頂點v的最短路徑。并且，如果不止一條，它要為頂點v找出兩條不同的最短路徑，否則報告不存在。請證明算法的正確性。解: 我們先用Dijkstra算法得到一棵以源點s為根的最短路徑樹T。樹T中，從源點s到每個頂點v的路徑是一條最短路徑，長度是d(v)。為方便，我們假定，源點s有路徑到達所有頂點。讓我們?nèi)∫稽cv來考慮。假設(shè)頂點u是v的一個反向鄰居，而且d(u)+w(u,v)=d(v)，那么從源點s到頂點u，再到頂點v就是一條最短路徑。進一步，如果從源點s到頂點u有h條最短路徑，那么頂點u就可以向頂點v提供h條最短路徑。反之，如果有一條從源點s到頂點v的最短路徑<s,u1,u2,…,uk,v>，那么，頂點uk必定是v的反向鄰居，路徑<s,u1,u2,…,uk>必定是從源點s到頂點uk的最短路徑，并且有d(uk)+w(uk,v)=d(v)。讓我們定義N(v)為從源點s到頂點v的不同的最短路徑個數(shù)，那么，我們有以下歸納公式：N(s)=1，N(v)=d(u)+wu,v由以上觀察，我們下面的算法判斷有幾條不同的從源點s到頂點v的最短路徑。由上面討論，正確性顯然。Number-of-Shortest-Path(G(V,E),s)SSP-Dijkstra(G(V,E),s) //求最短路徑樹T，p(s,v)是最短路徑，(s,v)=d(v)G’(V,E’)T(V(A),A) //復(fù)制一個最短路徑樹TEE–A //樹T以外的邊的集合foreachedge(u,v)E ifd(u)+w(u,v)=d(v) thenE’E’{(u,v)} //在樹里加上這些邊 endifendfor //顯然，G’(V,E’)不含回路Topological-Sort(G’(V,E’))Let<v1,v2,…,vn>bethesequencefromTopological-Sort //顯然有v1=sN(v1)1fori2ton N(vi)0 //初始化endforfori1ton-1 foreachvAdj(vi) N(v)N(v)+N(vi) endforendforcompute(G’)T //找G’的轉(zhuǎn)置矩陣以便找到反向鄰居Adj-(v)fori1ton //下面報告兩條最短路徑 ifN(vi)=1 thenreturn(Onlyonepathp(s,vi)) //p(s,vi)是最短路徑樹里路徑 else if|Adj-(v)|2 //點v有兩個反向鄰居 thenchoosetwobackwardneighbors,u1andu2 Path-1(v)p(s,u1){(u1,v)} Path-2(v)p(s,u2){(u2,v)} outputPath-1(v),Path-2(v) else u(v) //u是最短路徑樹里v的父親 Path-1(v)Path-1(u){(u,v)} Path-2(v)Path-2(u){(u,v)} outputPath-1(v),Path-2(v) endif endifendforEnd因為報告一條路徑需要O(n)時間，所以算法有復(fù)雜度O(n2)。假設(shè)有向圖G(V,E)中每條邊(u,v)的權(quán)值是正數(shù)，w(u,v)>0。另外，每個頂點v也有一個正數(shù)的權(quán)值w(v)>0。圖中一條從點s到點u的路徑p(s,u)的長度定義為路徑上所有頂點和邊的權(quán)值總和，包括點s和點u，即w(p(s,u))=v∈p(s,u)wv+(a,b)∈p(s,u)w(a,b)。對于這樣定義的路徑長度，請設(shè)計一個與Dijkstra算法有相同復(fù)雜度的算法，為有向圖G(V,E)計算以頂點s解：我們只需稍稍改動Dijkstra算法即可。因為很簡單，改動處在偽碼中說明。算法偽碼如下：SSP-with-Weighted-Vertices(G(V,E),s)foreachv?V d(v)?￥p(v)?nilendford(s)?w(s) //改動處1，d(s)初始值從0改為它的權(quán)值w(s)V(A)? A Q?