數(shù)據(jù)結(jié)構(gòu)第七講(4)最短路徑

1、n7.6 關(guān)鍵路徑關(guān)鍵路徑u問題提出問題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動；把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始每個事件表示在它之前的活動已完成，在它之后的活動可以開始例例 設(shè)一個工程有設(shè)一個工程有11項(xiàng)活動，項(xiàng)活動，9個事件個事件事件事件 V1表示整個工程開始表示整個工程開始事件事件V9表示整個工程結(jié)束表示整個工程結(jié)束問題：（問題：（1）完成整項(xiàng)工程至少需要多少時間？）完成整項(xiàng)工程至少需要多少時間？ （2）哪些活動是影響工程進(jìn)度的關(guān)鍵？）哪些活動是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4

2、a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4u定義定義FAOE網(wǎng)網(wǎng)(Activity On Edge)也叫邊表示活也叫邊表示活動的網(wǎng)。動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持中頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持續(xù)時間續(xù)時間F路徑長度路徑長度路徑上各活動持續(xù)時間之和路徑上各活動持續(xù)時間之和F關(guān)鍵路徑關(guān)鍵路徑路徑長度最長的路徑叫路徑長度最長的路徑叫FVe(j)表示事件表示事件Vj的最早發(fā)生時間的最早發(fā)生時間FVl(j)表示事件表示事件Vj的最遲發(fā)生時間的最遲發(fā)生時間Fe(i)表示活動表示活動a

3、i的最早開始時間的最早開始時間Fl(i)表示活動表示活動ai的最遲開始時間的最遲開始時間Fl(i)-e(i)表示完成活動表示完成活動ai的時間余量的時間余量F關(guān)鍵活動關(guān)鍵活動關(guān)鍵路徑上的活動叫關(guān)鍵路徑上的活動叫，即，即l(i)=e(i)的活動的活動u問題分析問題分析F如何找如何找e(i)=l(i)的關(guān)鍵活動？的關(guān)鍵活動？設(shè)活動設(shè)活動ai用弧用弧表示，其持續(xù)時間記為：表示，其持續(xù)時間記為：dut()則有：（則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiF如何求如何求Ve(j)和和Vl(j)？(1)從從Ve(1)=0開始向前遞推開始向前遞推為頭的弧的集合是所有以其

4、中jTnjTjijidutiVeMaxjVei2 ,),()()(2)從從Vl(n)=Ve(n)開始向后遞推開始向后遞推為尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(u求關(guān)鍵路徑步驟F求Ve(i)F求Vl(j)F求e(i)F求l(i)F計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn) Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e00002266

5、046258377077071031616014140033n7.7 最短路徑u問題提出用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)頂點(diǎn)表示城市表示城市邊邊表示城市間的交通聯(lián)系表示城市間的交通聯(lián)系權(quán)權(quán)表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑各邊上權(quán)值之和最小的一條路徑最短路徑最短路徑u從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑5164320856230137173291

6、3長度最短路徑813192120F迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：按路徑長度遞增次序產(chǎn)生最短路徑算法：把把V分成兩組：分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合：尚未確定最短路徑的頂點(diǎn)集合將將T中頂點(diǎn)按最短路徑遞增的次序加入到中頂點(diǎn)按最短路徑遞增的次序加入到S中，中，保證：（保證：（1）從源點(diǎn)）從源點(diǎn)V0到到S中各頂點(diǎn)的最短路徑長度都不大于中各頂點(diǎn)的最短路徑長度都不大于 從從V0到到T中任何頂點(diǎn)的最短路徑長度中任何頂點(diǎn)的最短路徑長度 （2）每個頂點(diǎn)對應(yīng)一個距離值）每個頂點(diǎn)對應(yīng)一

7、個距離值 S中頂點(diǎn)：從中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度到此頂點(diǎn)的最短路徑長度 T中頂點(diǎn)：從中頂點(diǎn)：從V0到此頂點(diǎn)的只包括到此頂點(diǎn)的只包括S中頂點(diǎn)作中間中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長度頂點(diǎn)的最短路徑長度依據(jù)：可以證明依據(jù)：可以證明V0到到T中頂點(diǎn)中頂點(diǎn)Vk的最短路徑，或是從的最短路徑，或是從V0到到Vk的的 直接路徑的權(quán)值；或是從直接路徑的權(quán)值；或是從V0經(jīng)經(jīng)S中頂點(diǎn)到中頂點(diǎn)到Vk的路徑權(quán)值之和的路徑權(quán)值之和（反證法可證）（反證法可證）ShortestPath ( const int n, const int v ) for ( int i = 0; i n; i+) disti = Edg

8、evi; /dist數(shù)組初始化數(shù)組初始化 Si = 0; if ( i != v & disti MAXINT ) pathi = v; else pathi = -1; /path數(shù)組初始化數(shù)組初始化 Sv = 1; distv = 0;/頂點(diǎn)頂點(diǎn)v加入頂點(diǎn)集合加入頂點(diǎn)集合 /選擇當(dāng)前不在集合選擇當(dāng)前不在集合S中具有最短路徑的頂點(diǎn)中具有最短路徑的頂點(diǎn)u for ( i = 0; i n-1; i+ ) int min = MAXINT; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; mi

9、n = distj; Su = 1; /將頂點(diǎn)將頂點(diǎn)u加入集合加入集合S for ( int w = 0; w n; w+ ) /修改修改 if ( !Sw & Edgeuw MAXINT & distu + Edgeuw distw ) distw = distu + Edgeuw; pathw = u; 138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19終點(diǎn)終點(diǎn) 從從V0到各終點(diǎn)的最短路徑及其長度到各終點(diǎn)的最短路徑及其長度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329u每一

10、對頂點(diǎn)之間的最短路徑F方法一：每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次 T(n)=O(n)F方法二：弗洛伊德(Floyd)算法 算法思想：逐個頂點(diǎn)試探法 求最短路徑步驟初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧，則對應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束F對于每一對頂點(diǎn) u 和 v，看看是否存在一個頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。F不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。F/ dist(i,j) 為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離FFor i1 to n do F For j1 to n do F dist(i,j) = weight(i,j)F For k1 to n do / k為“中間節(jié)點(diǎn)” F if (dist(i,k) + dist(k,j) dist(i,j) F then / 是否是更短的路徑？F dist(i,j) = dist(i,k) + dist(k,j)例ACB