11八月2023第1頁最短路徑、關(guān)鍵路徑及其應(yīng)用01八月2023第1頁1

所謂最短路徑問題是指：如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）出發(fā)到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和達(dá)到最小。

最短路徑問題所謂最短路徑問題是指：如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）出發(fā)2求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑11八月2023第3頁

每一對頂點(diǎn)之間的最短路徑求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑01八月2023第3頁311八月2023第4頁

求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:

依最短路徑的長度遞增的次序求得各條路徑源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)v的最短路徑是所有路徑中長度最短者。v201八月2023第4頁求從源點(diǎn)到其余各點(diǎn)的最4

給定帶權(quán)有向圖G和源點(diǎn)v,求從v到G中其余各頂點(diǎn)的最短路徑。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始點(diǎn)終點(diǎn)D[i]最短路徑V1V2V3V4V5∞10∞30100∞10∞30100∞106030100∞106030100∞105030100(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V4,V3)(V0,V4)(V0,V5)∞10503090(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503090(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)給定帶權(quán)有向圖G和源點(diǎn)v,求從v到G中其余各頂點(diǎn)的511八月2023第6頁

在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長度次短的最短路徑的特點(diǎn)：路徑長度最短的最短路徑的特點(diǎn)：

它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。01八月2023第6頁在這條路徑上，必定只含一條弧611八月2023第7頁其余最短路徑的特點(diǎn)：再下一條路徑長度次短的最短路徑的特點(diǎn):

它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。

它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。01八月2023第7頁其余最短路徑的特點(diǎn)：再下一條路徑長7如何在計(jì)算機(jī)中求得最短路徑？如何在計(jì)算機(jī)中求得最短路徑？811八月2023第9頁求最短路徑的迪杰斯特拉算法：一般情況下，Dist[k]=<源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>

或者=<源點(diǎn)到其它頂點(diǎn)的路徑長度>

+<其它頂點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>。

設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[k]表示

當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑。01八月2023第9頁求最短路徑的迪杰斯特拉算法：一般情9Dijkstra提出了一個(gè)按路徑“長度”遞增的次序，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑的算法：假設(shè)我們以鄰接矩陣cost表示所研究的有向網(wǎng)。迪杰斯特拉算法需要一個(gè)頂點(diǎn)集合，初始時(shí)集合內(nèi)只有一個(gè)源點(diǎn)V0，以后陸續(xù)將已求得最短路徑的頂點(diǎn)加入到集合中，到全部頂點(diǎn)都進(jìn)入集合了，過程就結(jié)束了。集合可用一維數(shù)組來表示，設(shè)此數(shù)組為S，凡在集合S以外的頂點(diǎn)，其相應(yīng)的數(shù)組元素S[i]為0，否則為1。Dijkstra提出了一個(gè)按路徑“長度”遞增的次序，10另需一個(gè)一維數(shù)組D，每個(gè)頂點(diǎn)對應(yīng)數(shù)組的一個(gè)單元，記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短路徑長度，其初值為D[i]=cost[V0][i]，i=1…n。數(shù)組D中的數(shù)據(jù)隨著算法的逐步進(jìn)行要不斷地修改定義了S集合和D數(shù)組并對其初始化后，迪杰斯特拉算法在進(jìn)行中，都是從S之外的頂點(diǎn)集合中選出一個(gè)頂點(diǎn)w，使D[w]的值最小。于是從源點(diǎn)到達(dá)w只通過S中的頂點(diǎn)，把w加入集合S中，并調(diào)整D中記錄的從源點(diǎn)到集合中每個(gè)頂點(diǎn)v的距離：取D[v]和D[w]+cost[w][v]中值較小的作為新的D[v]重復(fù)上述，直到S中包含V中其余各頂點(diǎn)的最短路徑。另需一個(gè)一維數(shù)組D，每個(gè)頂點(diǎn)對應(yīng)數(shù)組的一個(gè)單元，記錄從源點(diǎn)到11V0V1V2V3V4V5

V0∞∞10∞30100V1∞∞5∞∞∞V2∞∞∞50∞∞V3∞∞∞∞∞10V4∞∞∞20∞60V5∞∞∞∞∞∞{V0,V2,V4,V3,V5,V1}{V0,V2,V4,V3,V5}{V0,V2,V4,V3}{V0,V2,V4}{V0,V2}S={V0}V1V5V3V4V2VjV5V4V3V260305010∞60{V0,4,3,5}305010∞90{V0,4,5}3050{V0,4,3}10∞100{V0,5}30{V0,4}60{V0,2,3}10∞100{V0,5}30{V0,4}∞10{V0,2}∞V1i=5i=4i=3i=2i=1D終點(diǎn)V0V2V1V4V5V35503010101006020V0V1V2V3V4V1211八月2023第13頁1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Dist[k]值。假設(shè)求得最短路徑的頂點(diǎn)為u，若Dist[u]+G.arcs[u][k]<Dist[k]則將Dist[k]改為Dist[u]+G.arcs[u][k]。V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長度。01八月2023第13頁1）在所有從源點(diǎn)出發(fā)的弧中選取一1311八月2023第14頁求每一對頂點(diǎn)之間的最短路徑弗洛伊德算法的基本思想是：

從vi

到vj

的所有可能存在的路徑中，選出一條長度最短的路徑。01八月2023第14頁求每一對頂點(diǎn)之間的最短路徑弗洛伊1411八月2023第15頁若<vi,vj>存在，則存在路徑{vi,vj}//路徑中不含其它頂點(diǎn)若<vi,v1>,<v1,vj>存在，則存在路徑{vi,v1,vj}//路徑中所含頂點(diǎn)序號不大于1若{vi,…,v2},{v2,…,vj}存在，則存在一條路徑{vi,…,v2,…vj}//路徑中所含頂點(diǎn)序號不大于2…

依次類推，則vi至vj的最短路徑應(yīng)是上述這些路徑中，路徑長度最小者。01八月2023第15頁若<vi,vj>存在，則存在路徑15問題描述：

已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對每對頂點(diǎn)vi≠vj，要求求出每一對頂點(diǎn)之間的最短路徑和最短路徑長度。解決方案：1.每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對頂點(diǎn)之間的最短路徑。總的執(zhí)行時(shí)間為O(n3)。2.形式更直接的弗洛伊德（Floyd）算法。時(shí)間復(fù)雜度也為O(n3)。問題描述：

已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有16弗洛伊德算法思想：假設(shè)求從頂點(diǎn)Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長度為a[i][j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮路徑（Vi,V0,Vj）是否存在（即判別（Vi,V0）、（V0,Vj）是否存在）。如存在，則比較（Vi,Vj）和（Vi,V0,Vj）的路徑長度，取長度較短者為從Vi到Vj的中間頂點(diǎn)的序號不大于0的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn)V1，…依次類推?？赏瑫r(shí)求得各對頂點(diǎn)間的最短路徑。弗洛伊德算法思想：17定義一個(gè)n階方陣序列D(-1),D(0),D(1),D(2),…,D(k),…,D(n-1)其中：D(-1)[i][j]=a[i][j]D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}

0≤k≤n-1可見，D(1)[i][j]就是從vi到vj的中間頂點(diǎn)的序號不大于1的最短路徑的長度;D(k)[i][j]就是從vi到vj的中間頂點(diǎn)的序號不大于k的最短路徑的長度;D(n-1)[i][j]就是從vi到vj的最短路徑的長度。04116023∞0定義一個(gè)n階方陣序列041118

各頂點(diǎn)間的最短路徑及其路徑長度

最短路徑弗洛伊德舉例

04116023∞021CABCABCBCAABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400

320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB各頂點(diǎn)間的最短路徑及其路徑長度最短路徑弗洛伊德19

最短路徑導(dǎo)航查詢系統(tǒng)(圖)設(shè)計(jì)一個(gè)交通導(dǎo)航質(zhì)詢系統(tǒng)，能讓旅客質(zhì)詢從任一個(gè)城市頂點(diǎn)到另一個(gè)城市頂點(diǎn)之間的最短路徑問題。設(shè)計(jì)分為三個(gè)部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問題。

《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件20 該程序所做的工作是給司機(jī)們提供最佳路線，來提高能源和時(shí)間的合理利用。 此程序規(guī)定：1.把城市交通線路轉(zhuǎn)化為圖，從而對圖進(jìn)行相應(yīng)的結(jié)構(gòu)存儲；2.程序的輸出信息主要為：起始城市到目的城市的最短路徑； 3.程序的功能主要包括：城市之間路徑的存儲，最短路徑的計(jì)算，以及最短路徑和鄰接矩陣的輸出； 該程序所做的工作是給司機(jī)們提供最佳路線，來提高能源和時(shí)間的21概要設(shè)計(jì)對于這樣的問題，先假設(shè)有四個(gè)城市甲乙丙丁，甲乙相距2千米，且只有從乙到甲的單程線路。甲丙相距7千米，且只有從甲到丙的單程線路。甲丁相距4千米，且只有從甲到丁的單程線路。乙丙相距5千米，且只有從丙到乙的單程線路。乙丁相距3千米，且只有從丁到乙的單程線路。丙丁相距3千米，且只有從丁到丙的單程線路。戊甲相距6千米，且只有從戊到甲的單程線路。戊丁相距2千米，且只有從丁到戊的單程線路。乙己相距8千米，且只有從乙到己的單程線路。丙己相距6千米，且只有從己到丙的單程線路。編程出能求出個(gè)一點(diǎn)到任一點(diǎn)的最短路經(jīng)。概要設(shè)計(jì)22《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件23則圖G的鄰接矩陣為：

甲乙丙丁戊己甲∞∞74∞∞

乙2∞∞∞∞8

丙∞5∞∞∞∞

丁∞33∞2∞

戊6∞∞∞∞∞

己∞∞6∞∞∞則圖G的鄰接矩陣為：24系統(tǒng)用到的數(shù)據(jù)有：intwhich; intv; intendv;用到的主要函數(shù)：1）voidDispMat(MGraphg)//輸出鄰接矩陣g 2）voidppath(intpath[][MAXV],intv,intendv)//輸出相應(yīng)選擇的起點(diǎn)和終點(diǎn)的最短路 3）voidDisPath(intA[][MAXV],intpath[][MAXV],intn,intv,intendv)//由path計(jì)算最短路徑

《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件254）voidFloyd(MGraphg,intv,intendv)//采用弗洛伊德算法求沒對頂點(diǎn)之間的最短路徑5）intmain（）//主函數(shù)各程序模塊之間的調(diào)用關(guān)系： 函數(shù)3）可以調(diào)用函數(shù)2）。 函數(shù)4）可以調(diào)用函數(shù)3）。函數(shù)5）可以調(diào)用函數(shù)1）和函數(shù)4）。（具體程序略）《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件26首先運(yùn)行程序，包括三個(gè)選項(xiàng)，a.需要求最短路徑請按：1.b.輸出有向圖G的鄰接矩陣：2.c.退出系統(tǒng)請按：3.然后可以根據(jù)不同的需要選擇不同的選項(xiàng)進(jìn)行操作最后按3退出程序。首先運(yùn)行程序，包括三個(gè)選項(xiàng)，27測試丁和己測試丁和己2811八月2023第29頁

拓?fù)渑判?/p>

問題:

假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。

檢查有向圖中是否存在回路的方法之一，是對有向圖進(jìn)行拓?fù)渑判颉?1八月2023第29頁拓?fù)渑判騿栴}:2911八月2023第30頁何謂“拓?fù)渑判颉?？對有向圖進(jìn)行如下操作：

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。AOV（ActivityOnVertex）網(wǎng):就是頂點(diǎn)代表活動(dòng)，邊（狐）表示活動(dòng)的優(yōu)先關(guān)系的有向圖。01八月2023第30頁何謂“拓?fù)渑判颉?？對有向圖進(jìn)行如3011八月2023第31頁例如：對于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD

或

ACBD01八月2023第31頁例如：對于下列有向圖BDAC可求3111八月2023第32頁BDAC反之，對于下列有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)回路

{B,C,D}01八月2023第32頁BDAC反之，對于下列有向圖不能32施工從活動(dòng)a1、a2開始，到達(dá)活動(dòng)a8和a9時(shí)，整個(gè)施工結(jié)束。這類有向圖中，頂點(diǎn)表示活動(dòng)，弧<ai，aj>表示活動(dòng)ai優(yōu)先于活動(dòng)aj，稱這類有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)（AOV網(wǎng)）。AOV網(wǎng)(Activityonvertexnetwork)

一個(gè)有向圖可用來表示一個(gè)施工流程圖、一個(gè)產(chǎn)品生產(chǎn)流程圖、或一個(gè)程序框圖等。如圖：a1a5a4a6a2a3a8a7a9施工從活動(dòng)a1、a2開始，到達(dá)活動(dòng)a8和a9時(shí)，整個(gè)33AOV網(wǎng)可解決如下兩個(gè)問題：（1）判定工程的可行性。顯然，有回路，整個(gè)工程就無法結(jié)束（2）確定各項(xiàng)活動(dòng)在整個(gè)工程執(zhí)行中的先后順序稱這種先后順序?yàn)橥負(fù)溆行蛐蛄?。如圖有如下拓?fù)溆行蛐蛄校篴1a2a3a4a5a6a7a8a9

a2a6a1a3a4a5a7a9a8a1a5a4a6a2a3a8a7a9AOV網(wǎng)可解決如下兩個(gè)問題：如圖有如下拓?fù)溆行蛐蛄校篴13411八月2023第35頁如何進(jìn)行拓?fù)渑判?？一、從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之；

重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所

有以它為尾的?。?1八月2023第35頁如何進(jìn)行拓?fù)渑判?？一、從有向圖中3511八月2023第36頁abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點(diǎn)

入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧

弧頭頂點(diǎn)的入度減101八月2023第36頁abcghdfeabhcdgfe36由此分析知：拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)與頂點(diǎn)的入度有密切關(guān)系，因此，在選取存儲結(jié)構(gòu)時(shí)，應(yīng)考慮：能容易得到各頂點(diǎn)的入度；有利于尋找任一頂點(diǎn)的所有直接后繼。為此，采用鄰接表作為AOV網(wǎng)的存儲結(jié)構(gòu)，并在頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域（indegree）

由此分析知：拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)與頂點(diǎn)的入度有密切關(guān)系，因此，3711八月2023第38頁取入度為零的頂點(diǎn)v;while(v<>0){

printf(v);++m;w:=FirstAdj(v);

while(w<>0){inDegree[w]--;w:=nextAdj(v,w);

}

取下一個(gè)入度為零的頂點(diǎn)v;}ifm<nprintf(“圖中有回路”);算法描述01八月2023第38頁取入度為零的頂點(diǎn)v;算法描述3811八月2023第39頁

為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個(gè)“?！?，以保存“入度為零”的頂點(diǎn)。CountInDegree(G,indegree);//對各頂點(diǎn)求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);//入度為零的頂點(diǎn)入棧01八月2023第39頁為避免每次都要搜3911八月2023第40頁count=0;//對輸出頂點(diǎn)計(jì)數(shù)while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧頭頂點(diǎn)的入度減一

if(!indegree[w])Push(S,w);

//新產(chǎn)生的入度為零的頂點(diǎn)入棧

}}if(count<G.vexnum)printf(“圖中有回路”)01八月2023第40頁count=0;40《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件41c1c9c4c2c12c10c11c5c3c6c7c8將表轉(zhuǎn)換成圖c1c9c4c2c12c10c11c5c3c6c7c8將表轉(zhuǎn)42c1c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶1,c9c1c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫?3c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶1,c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶144c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶1,c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶145c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶146c12c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11c12c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,47c12c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11,c3,c12,c6c12c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,48c5c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11,c3,c12,c6c5c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c1149c5c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8c5c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c1150c1c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫蛄校篶1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8c1c9c4c2c12c10c11c5c3c6c7c8拓?fù)湫?111八月2023第52頁

關(guān)鍵路徑問題:

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。01八月2023第52頁關(guān)鍵路徑問題:52一、AOE網(wǎng)可解決如下問題：估算工程的最短工期（從源點(diǎn)到匯點(diǎn)至少需要多少時(shí)間）找出哪些活動(dòng)是影響整個(gè)工程進(jìn)展的關(guān)鍵①②③⑤a1=6a4=1a2=4a5=1有4個(gè)事件：V1，V2，V3，V5V1為源點(diǎn)，V5為匯點(diǎn)有4個(gè)活動(dòng)：a1,a2,a4,a5V3表示：a2已完成，a5可以開始一、AOE網(wǎng)可解決如下問題：①②③⑤a1=6a4=1a2=453二、關(guān)鍵路徑幾個(gè)術(shù)語路徑長度：路徑上各活動(dòng)持續(xù)時(shí)間的總和（即：路徑上所有弧的權(quán)值之和）關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)之間路徑長度最長的路徑（不一定唯一）事件Vi的最早發(fā)生時(shí)間ve(i)：從源點(diǎn)到Vi的最長路徑長度活動(dòng)ai的最早開始時(shí)間e(i)：等于該活動(dòng)的弧尾事件Vj的最早發(fā)生時(shí)間即若<j,k>表示活動(dòng)ai，則有e(i)=ve(j)vjvkai二、關(guān)鍵路徑幾個(gè)術(shù)語vjvkai54事件vk的最遲發(fā)生時(shí)間vl(k)：是在不推遲整個(gè)工期的前提下，該事件最遲必須發(fā)生的時(shí)間活動(dòng)ai的最遲開始時(shí)間L(i)：是該活動(dòng)的弧頭事件的最遲發(fā)生時(shí)間與該活動(dòng)的持續(xù)時(shí)間之差，即L(i)=vl(k)-ai的持續(xù)時(shí)間關(guān)鍵活動(dòng)：l(i)=e(i)的活動(dòng)由此可見：在AOE網(wǎng)中找關(guān)鍵活動(dòng)問題可轉(zhuǎn)化為求l(i)=e(i)，而e(i)=ve(j)l(i)=vl(k)-ai的持續(xù)時(shí)間因此，需先求出事件的最早、最遲發(fā)生時(shí)間事件vk的最遲發(fā)生時(shí)間vl(k)：是在不推遲整個(gè)工期的55

關(guān)鍵路徑三、關(guān)鍵路徑算法思想1.從ve(1)=0開始利用下面遞推公式，計(jì)算出各事件的最早發(fā)生時(shí)間ve(j)=Max{ve(i)+dut(<i,j>)}，j=2,……,n，<i,j>∈T其中：T是所有以j為頭的弧集合dut(<i,j>)表示活動(dòng)的持續(xù)時(shí)間前例中，ve(5)=Max{ve(2)+dut(<2,5>)，ve(3)+dut(<3,5>)}=Max{6+1,4+1}=7①②③⑤a1=6a4=1a2=4a5=1關(guān)鍵路徑三、關(guān)鍵路徑算法思想①②③⑤a1=6a4=1a2=562.從vl(n)=ve(n)開始，利用下面遞推公式，計(jì)算出各事件的最遲發(fā)生時(shí)間：vl(i)=Min{vl(j)-dut(<i,j>)}i=n-1,……,2,1,<i,j>∈S其中：S是所有以i為尾的弧集合關(guān)鍵路徑2.從vl(n)=ve(n)開始，利用下面遞推公式，計(jì)算57

關(guān)鍵路徑3.設(shè)活動(dòng)ai由弧<j,k>表示，其持續(xù)時(shí)間為dut(<j,k>)，則利用下面公式，計(jì)算出各活動(dòng)的最早、最遲開始時(shí)間：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)4.找出e(i)=l(i)的活動(dòng)，即為關(guān)鍵活動(dòng)，諸關(guān)鍵活動(dòng)組成的從源點(diǎn)到匯點(diǎn)的路徑即為關(guān)鍵路徑j(luò)kai=dut(<j,k>)關(guān)鍵路徑j(luò)kai=dut(<j,k>)58四、例子計(jì)算結(jié)果為：頂點(diǎn)VeVl活動(dòng)弧持續(xù)Tell-e關(guān)鍵活動(dòng)

V100a1<1,2>3011V234a2<1,3>2000a2V322a3<2.4>2341V466a4<2,5>3341V567a5<3,4>4220a5V688a6<3,6>3253a7<4,6>2660a7Max+Min-

a8<5,6>1671①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2四、例子計(jì)算結(jié)果為：①②③④⑤⑥a4=3a2=2a1=3a559關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)?？s短非關(guān)鍵活動(dòng)都不能縮短整個(gè)工期如a6縮短為1，則整個(gè)工期仍為8。又如a6推遲3天開始，或拖延3天完成（a6=6）均不影響整個(gè)工期①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。①②③④⑤⑥a4=3a2=2a60分析關(guān)鍵路徑的目的是找出影響整個(gè)工期的關(guān)鍵活動(dòng)，縮短關(guān)鍵活動(dòng)的持續(xù)時(shí)間，常可以縮短整個(gè)工期。如a7縮短為1，則整個(gè)工期為7。此時(shí)，再縮短任一關(guān)鍵活動(dòng)均不能縮短整個(gè)工期。即在有多條關(guān)鍵路徑時(shí)，縮短那些在所有關(guān)鍵路上的關(guān)鍵活動(dòng)，才能縮短整個(gè)工期①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2分析關(guān)鍵路徑的目的是找出影響整個(gè)工期的關(guān)鍵活動(dòng)，縮短關(guān)鍵活動(dòng)61v1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最遲發(fā)生時(shí)間vl[i]頂點(diǎn)序號viv1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最62v1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最遲發(fā)生時(shí)間vl[i]頂點(diǎn)序號via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最63v1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最遲發(fā)生時(shí)間vl[i]頂點(diǎn)序號via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4006650467778161618181414e[i]=ve[j]L[i]=vl[k]-dut<j,k>v1v3v4v5v6v7v8v2v9最早發(fā)生時(shí)間ve[i]最6411八月2023第65頁abcdefghk64521187244又例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加

將使有向圖上的最長路徑的長度增加。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑。源點(diǎn)匯點(diǎn)617401八月2023第65頁abcdefghk64521186511八月2023第66頁abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k01八月2023第66頁abcdefghk64521186611八月2023第67頁064577151418181416107866000064577715141416023668871001八月2023第67頁06457715141818146711八月2023第68頁

算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡颍?/p>

而求vl的順序應(yīng)該是按拓?fù)淠嫘虻拇涡?；因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄校虼藨?yīng)該在拓?fù)渑判虻倪^程中，另設(shè)一個(gè)“?！庇浵峦?fù)溆行蛐蛄小?1八月2023第68頁算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的68下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需的時(shí)問（其中“一”表示無先驅(qū)工序），請完成以下各題： (1)

畫出相應(yīng)的AOE網(wǎng)。 (2)

列出各事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間。 (3)

求出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。實(shí)例實(shí)例69《數(shù)據(jù)結(jié)構(gòu)》最短路徑關(guān)鍵路徑及其應(yīng)用解析ppt課件70 試題考核AOE網(wǎng)和關(guān)鍵路徑問題。要求熟悉AOE網(wǎng)的概念和如何求關(guān)鍵路徑的方法及步驟。 (1)

根據(jù)表的數(shù)據(jù)，可得AOE網(wǎng)，如圖所示。 試題考核AOE網(wǎng)和關(guān)鍵路徑問題。要求熟悉AOE網(wǎng)的概念和如71

(2)

所有事件的最早發(fā)生時(shí)間ve，如下所示：ve（v1）＝0

，ve（v2）＝3

，ve（v3）＝2ve（v4）＝Max{ve（v2）+2，ve（v3）+4}＝6

ve（v5）＝ve（v2）＋3＝6

，

ve（v6）＝Max{ve（v3）+3，ve（v4）+2，ve（v5）+1}＝8

所有事件的最遲發(fā)生時(shí)間vl，如下所示：vl（v6）＝8

，

vl（v5）＝vl（v6）－1＝7

vl（v4）＝vl（v6）－2＝6，vl（v3）＝Min{vl（v4）－4，vl（v6）－3}＝2

72vl（v2）＝Min{vl（v4）－2，vl（v5）－3}＝4vl（v1）＝Min{vl（v2）－3，vl（v3）－2}＝0(3)

求所有活動(dòng)的最早發(fā)生時(shí)間e、最遲發(fā)生時(shí)間l和時(shí)間余量l-e。 e（A）＝ve（v1）＝0

l（A）＝vl（v2）－3＝1

l（A）－e（A）＝1 e（B）＝ve（v1）＝0