數(shù)據(jù)結(jié)構(gòu)

第四十一課拓?fù)渑判蚝完P(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)

第四十一課拓?fù)渑判蚝完P(guān)鍵路徑1第三十三課拓?fù)渑判蚝完P(guān)鍵路徑本課主題：拓?fù)渑判蚝完P(guān)鍵路徑教學(xué)目的：拓?fù)渑判蚝完P(guān)鍵路徑教學(xué)重點：關(guān)鍵路徑教學(xué)難點：關(guān)鍵路徑授課內(nèi)容：第三十三課拓?fù)渑判蚝完P(guān)鍵路徑本課主題：拓?fù)渑判蚝完P(guān)鍵路2有向無環(huán)圖的概念有向無環(huán)圖的定義無環(huán)的有向圖叫有向無環(huán)圖，簡稱DAG圖。有向無環(huán)圖的應(yīng)用有向無環(huán)圖是描述工程或系統(tǒng)的進(jìn)行過程的有效工具。一是工程能否順利進(jìn)行，二是估算工程完成所需的最短時間，這就是拓?fù)渑判蚝完P(guān)鍵路徑問題。有向無環(huán)圖的概念有向無環(huán)圖的定義3一﹑拓?fù)渑判?、拓?fù)渑判虻幕靖拍?1)AOV網(wǎng)頂點表示活動，弧表示活動間的優(yōu)先關(guān)系的有向圖，叫頂點表示活動的網(wǎng)（ActivityOnVertexNetwork）。(2)拓?fù)湫蛄袑OV網(wǎng)上的所以頂點排成一個線性序列，且該序列滿足若在AOV網(wǎng)中，頂點vi到vj有一條路徑，則在該線性序列中vi必在vj的前面。這樣的序列稱為拓?fù)湫蛄小Ｒ哗p拓?fù)渑判?、拓?fù)渑判虻幕靖拍?(3)拓?fù)渑判驅(qū)OV網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鹘型負(fù)渑判颉?4)在AOV網(wǎng)中不應(yīng)有環(huán)，否則就會自己以自己為先決條件；若AOV網(wǎng)代表一個工程，則AOV網(wǎng)的一個拓?fù)湫蛄芯褪且粋€工程順利完成的可行方案。(3)拓?fù)渑判?2、拓?fù)渑判虻姆椒◤膱D中選擇一個入度為0的頂點輸出；從圖中刪除該頂點及源自該頂點的所有弧；重復(fù)以上兩步，直至全部頂點都輸出，拓?fù)渑判蝽樌瓿伞７駝t，若剩有入度非0的頂點，說明圖中有環(huán)，拓?fù)渑判虿荒苓M(jìn)行。2、拓?fù)渑判虻姆椒◤膱D中選擇一個入度為0的頂點輸出；63﹑拓?fù)渑判蛩惴?1)在鄰接表的頂點向量中，向量的每個元素再增加一個入度域，存放各頂點的入度值。輸出該頂點，刪除源自該頂點的弧就是將該頂點的鄰接點的入度減1。實際實現(xiàn)時，可設(shè)一個棧，存放入度為0的頂點，退棧就是輸出頂點，當(dāng)鄰接點的入度域減1減到0時，就將其入棧，拓?fù)渑判蛲瓿蓵r，棧應(yīng)為空。3﹑拓?fù)渑判蛩惴?1)在鄰接表的頂點向量中，向量的每個元素再73、拓?fù)渑判蛩惴?2)StatusToplogicalSort(ALGraphG){FindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);count=0;

3、拓?fù)渑判蛩惴?2)StatusToplogicalS83、拓?fù)渑判蛩惴?3)while(!StackEmpty(S)){Pop(S,i);printf(I,G.vertices[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p>adjvex;if(!(--indegree[k]))Push(S,k);}}if(count<G.vexnum)returnERROR;elsereturnOK;}3、拓?fù)渑判蛩惴?3)while(!StackEmpty(94、拓?fù)渑判蛩惴ǖ姆治鯫（n+e）4、拓?fù)渑判蛩惴ǖ姆治鯫（n+e）10二﹑關(guān)鍵路徑1﹑AOE網(wǎng)用頂點表示事件，弧表示活動，弧上的權(quán)值表示活動持續(xù)的時間的有向圖叫AOE（ActivityOnEdgeNetwork）網(wǎng)。AOE網(wǎng)常用于估算工程完成時間。二﹑關(guān)鍵路徑1﹑AOE網(wǎng)112﹑AOE網(wǎng)研究的問題完成整個工程至少需要多少時間；哪些活動是影響工程的關(guān)鍵。1956年，美國杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬美圓化工廠建設(shè)，工期比原計劃縮短了4個月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬美圓。2﹑AOE網(wǎng)研究的問題完成整個工程至少需要多少時間；123﹑關(guān)鍵路徑的幾個術(shù)語關(guān)鍵路徑從源點到匯點的路徑長度最長的路徑叫關(guān)鍵路徑。活動開始的最早時間e(i)活動開始的最晚時間l(i)定義e(i)=l(i)的活動叫關(guān)鍵活動。事件開始的最早時間ve(i)事件開始的最晚時間vl(i)3﹑關(guān)鍵路徑的幾個術(shù)語關(guān)鍵路徑從源點到匯點的路徑長度最長13設(shè)活動ai由弧<j,k>(即從頂點j到k)表示，其持續(xù)時間記為dut(<j,k>),則e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)(6_6_1)求ve(i)和vl(j)分兩步：從ve(1)=0開始向前遞推ve(j)=Max{ve(i)+dut(<i,j>)}(6_6_2)<i,j>∈T,2≤j≤n,其中T是所有以j為弧頭的弧的集合。從vl(n)=ve(n)開始向后遞推vl(i)=Min{vl(j)-dut(<i,j>)}(6_6_3)<i,j>∈S,1≤i≤n-1,其中S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。設(shè)活動ai由弧<j,k>(即從頂點j到k)表示，其持續(xù)時間記144﹑求關(guān)鍵路徑的算法(1)輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。從源點v1出發(fā)，令ve(1)=0,求ve(j)2<=j<=n。從匯點vn出發(fā)，令vl(n)=ve(n),求vl(i)1<=i<=n-1。根據(jù)各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關(guān)鍵活動。

求關(guān)鍵路徑是在拓?fù)渑判虻那疤嵯逻M(jìn)行的，不能進(jìn)行拓?fù)渑判颍匀灰膊荒芮箨P(guān)鍵路徑。4﹑求關(guān)鍵路徑的算法(1)輸入e條弧<j,k>，建立AOE網(wǎng)154﹑求關(guān)鍵路徑的算法(2)StatusToplogicalSort(ALGraphG,stack&T){FindInDegree(G,indegree);InitStack(S);count=0;ve[0..G.vexnum-1]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p>adjvex;if(--indegree[k]==0)Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}

4﹑求關(guān)鍵路徑的算法(2)StatusToplogical164﹑求關(guān)鍵路徑的算法(3)if(count<G.vexnum)returnERROR;elsereturnOK;}statusCriticalPath(ALGraphG){if(!ToplogicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[0..G.vexnum-1];while(!StackEmpty(T))for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p>adjvex;dut=*(p->info);if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}

4﹑求關(guān)鍵路徑的算法(3)if(count<G.vexnum174﹑求關(guān)鍵路徑的算法(4)for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p>adjvex;dut=*(p->info);ee=ve[j];el=vl[k];tag=(ee==el)?’*’:’’;printf(j,kdut,ee,el,tag);}}4﹑求關(guān)鍵路徑的算法(4)for(j=0;j<G.vexnu185﹑求關(guān)鍵路徑的實例模擬

5﹑求關(guān)鍵路徑的實例模擬196﹑求關(guān)鍵路徑的算法分析求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑；只有縮短關(guān)鍵活動的工期才有可能縮短工期；若一個關(guān)鍵活動不在所有的關(guān)鍵路徑上，減少它并不能減少工期；只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動才能縮短整個工期。6﹑求關(guān)鍵路徑的算法分析求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行20六﹑總結(jié)回目錄

上一課

下一課六﹑總結(jié)21數(shù)據(jù)結(jié)構(gòu)

第四十一課拓?fù)渑判蚝完P(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)

第四十一課拓?fù)渑判蚝完P(guān)鍵路徑22第三十三課拓?fù)渑判蚝完P(guān)鍵路徑本課主題：拓?fù)渑判蚝完P(guān)鍵路徑教學(xué)目的：拓?fù)渑判蚝完P(guān)鍵路徑教學(xué)重點：關(guān)鍵路徑教學(xué)難點：關(guān)鍵路徑授課內(nèi)容：第三十三課拓?fù)渑判蚝完P(guān)鍵路徑本課主題：拓?fù)渑判蚝完P(guān)鍵路23有向無環(huán)圖的概念有向無環(huán)圖的定義無環(huán)的有向圖叫有向無環(huán)圖，簡稱DAG圖。有向無環(huán)圖的應(yīng)用有向無環(huán)圖是描述工程或系統(tǒng)的進(jìn)行過程的有效工具。一是工程能否順利進(jìn)行，二是估算工程完成所需的最短時間，這就是拓?fù)渑判蚝完P(guān)鍵路徑問題。有向無環(huán)圖的概念有向無環(huán)圖的定義24一﹑拓?fù)渑判?、拓?fù)渑判虻幕靖拍?1)AOV網(wǎng)頂點表示活動，弧表示活動間的優(yōu)先關(guān)系的有向圖，叫頂點表示活動的網(wǎng)（ActivityOnVertexNetwork）。(2)拓?fù)湫蛄袑OV網(wǎng)上的所以頂點排成一個線性序列，且該序列滿足若在AOV網(wǎng)中，頂點vi到vj有一條路徑，則在該線性序列中vi必在vj的前面。這樣的序列稱為拓?fù)湫蛄小Ｒ哗p拓?fù)渑判?、拓?fù)渑判虻幕靖拍?5(3)拓?fù)渑判驅(qū)OV網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鹘型負(fù)渑判颉?4)在AOV網(wǎng)中不應(yīng)有環(huán)，否則就會自己以自己為先決條件；若AOV網(wǎng)代表一個工程，則AOV網(wǎng)的一個拓?fù)湫蛄芯褪且粋€工程順利完成的可行方案。(3)拓?fù)渑判?62、拓?fù)渑判虻姆椒◤膱D中選擇一個入度為0的頂點輸出；從圖中刪除該頂點及源自該頂點的所有弧；重復(fù)以上兩步，直至全部頂點都輸出，拓?fù)渑判蝽樌瓿伞７駝t，若剩有入度非0的頂點，說明圖中有環(huán)，拓?fù)渑判虿荒苓M(jìn)行。2、拓?fù)渑判虻姆椒◤膱D中選擇一個入度為0的頂點輸出；273﹑拓?fù)渑判蛩惴?1)在鄰接表的頂點向量中，向量的每個元素再增加一個入度域，存放各頂點的入度值。輸出該頂點，刪除源自該頂點的弧就是將該頂點的鄰接點的入度減1。實際實現(xiàn)時，可設(shè)一個棧，存放入度為0的頂點，退棧就是輸出頂點，當(dāng)鄰接點的入度域減1減到0時，就將其入棧，拓?fù)渑判蛲瓿蓵r，棧應(yīng)為空。3﹑拓?fù)渑判蛩惴?1)在鄰接表的頂點向量中，向量的每個元素再283、拓?fù)渑判蛩惴?2)StatusToplogicalSort(ALGraphG){FindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);count=0;

3、拓?fù)渑判蛩惴?2)StatusToplogicalS293、拓?fù)渑判蛩惴?3)while(!StackEmpty(S)){Pop(S,i);printf(I,G.vertices[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p>adjvex;if(!(--indegree[k]))Push(S,k);}}if(count<G.vexnum)returnERROR;elsereturnOK;}3、拓?fù)渑判蛩惴?3)while(!StackEmpty(304、拓?fù)渑判蛩惴ǖ姆治鯫（n+e）4、拓?fù)渑判蛩惴ǖ姆治鯫（n+e）31二﹑關(guān)鍵路徑1﹑AOE網(wǎng)用頂點表示事件，弧表示活動，弧上的權(quán)值表示活動持續(xù)的時間的有向圖叫AOE（ActivityOnEdgeNetwork）網(wǎng)。AOE網(wǎng)常用于估算工程完成時間。二﹑關(guān)鍵路徑1﹑AOE網(wǎng)322﹑AOE網(wǎng)研究的問題完成整個工程至少需要多少時間；哪些活動是影響工程的關(guān)鍵。1956年，美國杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬美圓化工廠建設(shè)，工期比原計劃縮短了4個月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬美圓。2﹑AOE網(wǎng)研究的問題完成整個工程至少需要多少時間；333﹑關(guān)鍵路徑的幾個術(shù)語關(guān)鍵路徑從源點到匯點的路徑長度最長的路徑叫關(guān)鍵路徑。活動開始的最早時間e(i)活動開始的最晚時間l(i)定義e(i)=l(i)的活動叫關(guān)鍵活動。事件開始的最早時間ve(i)事件開始的最晚時間vl(i)3﹑關(guān)鍵路徑的幾個術(shù)語關(guān)鍵路徑從源點到匯點的路徑長度最長34設(shè)活動ai由弧<j,k>(即從頂點j到k)表示，其持續(xù)時間記為dut(<j,k>),則e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)(6_6_1)求ve(i)和vl(j)分兩步：從ve(1)=0開始向前遞推ve(j)=Max{ve(i)+dut(<i,j>)}(6_6_2)<i,j>∈T,2≤j≤n,其中T是所有以j為弧頭的弧的集合。從vl(n)=ve(n)開始向后遞推vl(i)=Min{vl(j)-dut(<i,j>)}(6_6_3)<i,j>∈S,1≤i≤n-1,其中S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。設(shè)活動ai由弧<j,k>(即從頂點j到k)表示，其持續(xù)時間記354﹑求關(guān)鍵路徑的算法(1)輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。從源點v1出發(fā)，令ve(1)=0,求ve(j)2<=j<=n。從匯點vn出發(fā)，令vl(n)=ve(n),求vl(i)1<=i<=n-1。根據(jù)各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關(guān)鍵活動。

求關(guān)鍵路徑是在拓?fù)渑判虻那疤嵯逻M(jìn)行的，不能進(jìn)行拓?fù)渑判颍匀灰膊荒芮箨P(guān)鍵路徑。4﹑求關(guān)鍵路徑的算法(1)輸入e條弧<j,k>，建立AOE網(wǎng)364﹑求關(guān)鍵路徑的算法(2)StatusToplogicalSort(ALGraphG,stack&T){FindInDegree(G,indegree);InitStack(S);count=0;ve[0..G.vexnum-1]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p>adjvex;if(--indegree[k]==0)Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}

4﹑求關(guān)鍵路徑的算法(2)StatusToplogical374﹑求關(guān)鍵路徑的算法(3)if(count<G.vexnum)returnERROR;elseretu