貪婪算法---單源最短路徑

1、單源最短路徑在這個(gè)問(wèn)題中，給出有向圖G，它的每條邊都有一個(gè)非負(fù)的長(zhǎng)度（耗費(fèi)） a i j ，路徑的長(zhǎng)度即為此路徑所經(jīng)過(guò)的邊的長(zhǎng)度之和。對(duì)于給定的源頂點(diǎn)s，需找出從它到圖中其他任意頂點(diǎn)（稱(chēng)為目的）的最短路徑。圖13-10a 給出了一個(gè)具有五個(gè)頂點(diǎn)的有向圖，各邊上的數(shù)即為長(zhǎng)度。假設(shè)源頂點(diǎn)s 為1，從頂點(diǎn)1出發(fā)的最短路徑按路徑長(zhǎng)度順序列在圖13-10b 中，每條路徑前面的數(shù)字為路徑的長(zhǎng)度。利用E. Dijkstra發(fā)明的貪婪算法可以解決最短路徑問(wèn)題，它通過(guò)分步方法求出最短路徑。每一步產(chǎn)生一個(gè)到達(dá)新的目的頂點(diǎn)的最短路徑。下一步所能達(dá)到的目的頂點(diǎn)通過(guò)如下貪婪準(zhǔn)則選取：在還未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑

2、長(zhǎng)度最短的目的頂點(diǎn)。也就是說(shuō)， D i j k s t r a的方法按路徑長(zhǎng)度順序產(chǎn)生最短路徑。首先最初產(chǎn)生從s 到它自身的路徑，這條路徑?jīng)]有邊，其長(zhǎng)度為0。在貪婪算法的每一步中，產(chǎn)生下一個(gè)最短路徑。一種方法是在目前已產(chǎn)生的最短路徑中加入一條可行的最短的邊，結(jié)果產(chǎn)生的新路徑是原先產(chǎn)生的最短路徑加上一條邊。這種策略并不總是起作用。另一種方法是在目前產(chǎn)生的每一條最短路徑中，考慮加入一條最短的邊，再?gòu)乃羞@些邊中先選擇最短的，這種策略即是D i j k s t r a算法。可以驗(yàn)證按長(zhǎng)度順序產(chǎn)生最短路徑時(shí)，下一條最短路徑總是由一條已產(chǎn)生的最短路徑加上一條邊形成。實(shí)際上，下一條最短路徑總是由已產(chǎn)生的最

3、短路徑再擴(kuò)充一條最短的邊得到的，且這條路徑所到達(dá)的頂點(diǎn)其最短路徑還未產(chǎn)生。例如在圖1 3 - 1 0中，b 中第二條路徑是第一條路徑擴(kuò)充一條邊形成的；第三條路徑則是第二條路徑擴(kuò)充一條邊；第四條路徑是第一條路徑擴(kuò)充一條邊；第五條路徑是第三條路徑擴(kuò)充一條邊。通過(guò)上述觀察可用一種簡(jiǎn)便的方法來(lái)存儲(chǔ)最短路徑?？梢岳脭?shù)組p，p i 給出從s 到達(dá)i的路徑中頂點(diǎn)i 前面的那個(gè)頂點(diǎn)。在本例中p 1 : 5 = 0 , 1 , 1 , 3 , 4 。從s 到頂點(diǎn)i 的路徑可反向創(chuàng)建。從i 出發(fā)按pi,ppi,pppi, .的順序，直到到達(dá)頂點(diǎn)s 或0。在本例中，如果從i = 5開(kāi)始，則頂點(diǎn)序列為pi=4, p

4、4=3, p3=1=s，因此路徑為1 , 3 , 4 , 5。為能方便地按長(zhǎng)度遞增的順序產(chǎn)生最短路徑，定義d i 為在已產(chǎn)生的最短路徑中加入一條最短邊的長(zhǎng)度，從而使得擴(kuò)充的路徑到達(dá)頂點(diǎn)i。最初，僅有從s 到s 的一條長(zhǎng)度為0的路徑，這時(shí)對(duì)于每個(gè)頂點(diǎn)i，d i 等于a s i （a 是有向圖的長(zhǎng)度鄰接矩陣）。為產(chǎn)生下一條路徑，需要選擇還未產(chǎn)生最短路徑的下一個(gè)節(jié)點(diǎn)，在這些節(jié)點(diǎn)中d值最小的即為下一條路徑的終點(diǎn)。當(dāng)獲得一條新的最短路徑后，由于新的最短路徑可能會(huì)產(chǎn)生更小的d值，因此有些頂點(diǎn)的d值可能會(huì)發(fā)生變化。綜上所述，可以得到圖1 3 - 11所示的偽代碼， 1) 將與s 鄰接的所有頂點(diǎn)的p 初始化為

5、s，這個(gè)初始化用于記錄當(dāng)前可用的最好信息。也就是說(shuō)，從s 到i 的最短路徑，即是由s到它自身那條路徑再擴(kuò)充一條邊得到。當(dāng)找到更短的路徑時(shí)， p i 值將被更新。若產(chǎn)生了下一條最短路徑，需要根據(jù)路徑的擴(kuò)充邊來(lái)更新d 的值。1) 初始化di =as i （1in），對(duì)于鄰接于s的所有頂點(diǎn)i，置pi =s, 對(duì)于其余的頂點(diǎn)置pi = 0；對(duì)于pi0的所有頂點(diǎn)建立L表。2) 若L為空，終止，否則轉(zhuǎn)至3 )。3) 從L中刪除d值最小的頂點(diǎn)。4) 對(duì)于與i 鄰接的所有還未到達(dá)的頂點(diǎn)j，更新d j 值為m i nd j , di +ai j ；若d j 發(fā)生了變化且j 還未在L中，則置p j = 1，并將j

6、 加入L，轉(zhuǎn)至2。圖1 - 11 最短路徑算法的描述1. 數(shù)據(jù)結(jié)構(gòu)的選擇我們需要為未到達(dá)的頂點(diǎn)列表L選擇一個(gè)數(shù)據(jù)結(jié)構(gòu)。從L中可以選出d 值最小的頂點(diǎn)。如果L用最小堆（見(jiàn)9 . 3節(jié)）來(lái)維護(hù)，則這種選取可在對(duì)數(shù)時(shí)間內(nèi)完成。由于3) 的執(zhí)行次數(shù)為O ( n )，所以所需時(shí)間為O ( n l o g n )。由于擴(kuò)充一條邊產(chǎn)生新的最短路徑時(shí)，可能使未到達(dá)的頂點(diǎn)產(chǎn)生更小的d 值，所以在4) 中可能需要改變一些d 值。雖然算法中的減操作并不是標(biāo)準(zhǔn)的最小堆操作，但它能在對(duì)數(shù)時(shí)間內(nèi)完成。由于執(zhí)行減操作的總次數(shù)為： O(有向圖中的邊數(shù))= O ( n2 )，因此執(zhí)行減操作的總時(shí)間為O ( n2 l o g n

7、 )。若L用無(wú)序的鏈表來(lái)維護(hù)，則3) 與4) 花費(fèi)的時(shí)間為O ( n2 )，3) 的每次執(zhí)行需O(|L | ) =O( n )的時(shí)間，每次減操作需( 1 )的時(shí)間（需要減去dj 的值，但鏈表不用改變）。利用無(wú)序鏈表將圖1 - 11的偽代碼細(xì)化為程序1 3 - 5，其中使用了C h a i n (見(jiàn)程序3 - 8 )和C h a i n I t e r a t o r類(lèi)（見(jiàn)程序3 - 1 8）。程序13-5 最短路徑程序templatevoid AdjacencyWDigraph:ShortestPaths(int s, T d, int p)/ 尋找從頂點(diǎn)s出發(fā)的最短路徑, 在d中返回最短距離

8、/ 在p中返回前繼頂點(diǎn)if (s < 1 | s > n) throw OutOfBounds();Chain L; / 路徑可到達(dá)頂點(diǎn)的列表ChainIterator I;/ 初始化d, p, Lfor (int i = 1; i <= n; i+)di = asi;if (di = NoEdge) pi = 0;else pi = s;L . I n s e r t ( 0 , i ) ; / 更新d, pwhile (!L.IsEmpty() / 尋找具有最小d的頂點(diǎn)vint *v = I.Initialize(L);int *w = I.Next();while (w

9、) if (d*w < d*v) v = w;w = I.Next();/ 從L中刪除通向頂點(diǎn)v的下一最短路徑并更新dint i = *v;L . D e l e t e ( * v ) ;for (int j = 1; j <= n; j+) if (aij != NoEdge && (!pj |dj > di + aij) / 減小d j dj = di + aij;/ 將j加入Lif (!pj) L.Insert(0,j);pj = i;若N o E d g e足夠大，使得沒(méi)有最短路徑的長(zhǎng)度大于或等于N o E d g e，則最后一個(gè)for 循環(huán)的i f條件可簡(jiǎn)化為：if (dj > di + aij) NoEdge 的值應(yīng)在能使dj+aij 不會(huì)產(chǎn)生溢出的范圍內(nèi)。2. 復(fù)雜性分析程序1 3 - 5的復(fù)雜性是O ( n2 )，任何最短路徑算法必須至少對(duì)每條邊檢查一次，因?yàn)槿魏我粭l邊都有可能在最短路徑中。因此這種算法的最小可能時(shí)間為O ( e )。由于使用耗費(fèi)鄰接矩陣來(lái)描述圖，僅決定哪條邊在有向圖中就需O