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

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

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

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

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

5、s，這個初始化用于記錄當(dāng)前可用的最好信息。也就是說，從s 到i 的最短路徑，即是由s到它自身那條路徑再擴(kuò)充一條邊得到。當(dāng)找到更短的路徑時， p i 值將被更新。若產(chǎn)生了下一條最短路徑，需要根據(jù)路徑的擴(kuò)充邊來更新d 的值。1) 初始化di =as i （1in），對于鄰接于s的所有頂點i，置pi =s, 對于其余的頂點置pi = 0；對于pi0的所有頂點建立L表。2) 若L為空，終止，否則轉(zhuǎn)至3 )。3) 從L中刪除d值最小的頂點。4) 對于與i 鄰接的所有還未到達(dá)的頂點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á)的頂點列表L選擇一個數(shù)據(jù)結(jié)構(gòu)。從L中可以選出d 值最小的頂點。如果L用最小堆（見9 . 3節(jié)）來維護(hù)，則這種選取可在對數(shù)時間內(nèi)完成。由于3) 的執(zhí)行次數(shù)為O ( n )，所以所需時間為O ( n l o g n )。由于擴(kuò)充一條邊產(chǎn)生新的最短路徑時，可能使未到達(dá)的頂點產(chǎn)生更小的d 值，所以在4) 中可能需要改變一些d 值。雖然算法中的減操作并不是標(biāo)準(zhǔn)的最小堆操作，但它能在對數(shù)時間內(nèi)完成。由于執(zhí)行減操作的總次數(shù)為： O(有向圖中的邊數(shù))= O ( n2 )，因此執(zhí)行減操作的總時間為O ( n2 l o g n

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

8、/ 在p中返回前繼頂點if (s < 1 | s > n) throw OutOfBounds();Chain L; / 路徑可到達(dá)頂點的列表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的頂點vint *v = I.Initialize(L);int *w = I.Next();while (w

9、) if (d*w < d*v) v = w;w = I.Next();/ 從L中刪除通向頂點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足夠大，使得沒有最短路徑的長度大于或等于N o E d g e，則最后一個for 循環(huán)的i f條件可簡化為：if (dj > di + aij) NoEdge 的值應(yīng)在能使dj+aij 不會產(chǎn)生溢出的范圍內(nèi)。2. 復(fù)雜性分析程序1 3 - 5的復(fù)雜性是O ( n2 )，任何最短路徑算法必須至少對每條邊檢查一次，因為任何一條邊都有可能在最短路徑中。因此這種算法的最小可能時間為O ( e )。由于使用耗費鄰接矩陣來描述圖，僅決定哪條邊在有向圖中就需O