數(shù)據(jù)結(jié)構(gòu)與算法分析課件講義

數(shù)據(jù)結(jié)構(gòu)與算法分析第六章關(guān)鍵路徑（5）1謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)與算法分析第六章關(guān)鍵路徑（5）1謝謝觀賞2019-6.7關(guān)鍵路徑如何建立一個(gè)工程進(jìn)度控制模型？如何估算完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?人們用AOE網(wǎng)解決這個(gè)問題2謝謝觀賞2019-8-216.7關(guān)鍵路徑如何建立一個(gè)工程進(jìn)度控制模型？如何估算完成整AOE網(wǎng)（ActivityOnEdgeNetwork）在帶權(quán)的有向圖中，用結(jié)點(diǎn)表示事件：所有入邊上進(jìn)行的活動(dòng)均已完成的事件用邊表示活動(dòng)：起始結(jié)點(diǎn)事件發(fā)生后所開展的活動(dòng)邊的上權(quán)表示活動(dòng)的開銷（如持續(xù)時(shí)間）則稱此有向圖為“邊表示活動(dòng)的網(wǎng)絡(luò)”,簡(jiǎn)稱AOE網(wǎng)。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=103謝謝觀賞2019-8-21AOE網(wǎng)（ActivityOnEdgeNetwork）AOE網(wǎng)的性質(zhì)活動(dòng)開始時(shí)間：只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊代表的活動(dòng)才能開始;事件發(fā)生時(shí)間：只有在進(jìn)入某一頂點(diǎn)的各有向邊代表的活動(dòng)已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生；表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無環(huán)的，并且存在唯一的入度為0的開始頂點(diǎn)（源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（匯點(diǎn)）。4謝謝觀賞2019-8-21AOE網(wǎng)的性質(zhì)活動(dòng)開始時(shí)間：只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后AOE網(wǎng)研究的主要問題：

如果用AOE網(wǎng)表示一項(xiàng)工程，那么僅僅考慮各個(gè)子工程之間的優(yōu)先關(guān)系還不夠，更多地是關(guān)心整個(gè)工程完成的最短時(shí)間是多少，哪些活動(dòng)的延遲將影響整個(gè)工程進(jìn)度,而加速這些活動(dòng)能否提高整個(gè)工程的效率,因此AOE網(wǎng)有待研究的問題是:(1)完成整個(gè)工程至少需要多少時(shí)間？(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？5謝謝觀賞2019-8-21AOE網(wǎng)研究的主要問題：如果用AOE網(wǎng)表示一項(xiàng)工路徑長(zhǎng)度、關(guān)鍵路徑、關(guān)鍵活動(dòng)：路徑長(zhǎng)度：是指從源點(diǎn)到匯點(diǎn)路徑上所有活動(dòng)的持續(xù)時(shí)間之和。關(guān)鍵路徑：完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長(zhǎng)度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑。一個(gè)AOE中，關(guān)鍵路徑可能不只一條。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。在關(guān)鍵路徑長(zhǎng)度的范圍內(nèi)，可以安排并行的活動(dòng)6謝謝觀賞2019-8-21路徑長(zhǎng)度、關(guān)鍵路徑、關(guān)鍵活動(dòng)：6謝謝觀賞2019-8-21舉例：奧運(yùn)會(huì)競(jìng)賽日程地點(diǎn)：主會(huì)場(chǎng)需要考慮的場(chǎng)地：中心、跑道、沙坑需要考慮的項(xiàng)目：短跑、長(zhǎng)跑、馬拉松、鉛球、跳高、跳遠(yuǎn)。。。源點(diǎn)：開幕式;終點(diǎn):閉幕式7謝謝觀賞2019-8-21舉例：奧運(yùn)會(huì)競(jìng)賽日程地點(diǎn)：主會(huì)場(chǎng)7謝謝觀賞2019-8-21術(shù)語：ve(j),vl(j),e(i),l(i),ve(j):事件vj的最早發(fā)生時(shí)間。事件用v標(biāo)識(shí)，事件的編號(hào)用括號(hào)中的數(shù)字標(biāo)識(shí)，v的下標(biāo)區(qū)分“最早”和“最晚”。vl(j):事件vj的最晚發(fā)生時(shí)間。事件用“發(fā)生”描述。e(i):活動(dòng)ai的最早開始時(shí)間。沒有v的符號(hào)就是表示活動(dòng)，括號(hào)中是活動(dòng)的編號(hào)，e表示最早開始時(shí)間，l表示最晚。l(i):活動(dòng)ai的最晚開始時(shí)間?；顒?dòng)用“開始”8謝謝觀賞2019-8-21術(shù)語：ve(j),vl(j),e(i),l(i),veVe(j)：事件vj的最早發(fā)生時(shí)間Ve(j)＝從源點(diǎn)V1到頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10從源點(diǎn)到頂點(diǎn)Vj的最長(zhǎng)路徑，可以包括所有以頂點(diǎn)Vj為終點(diǎn)的全部活動(dòng)所需時(shí)間。經(jīng)過這段路徑，事件Vj才有可能發(fā)生。Ve(6)是多少？9謝謝觀賞2019-8-21Ve(j)：事件vj的最早發(fā)生時(shí)間Ve(j)＝從源點(diǎn)V1e(i):活動(dòng)ai的最早可能開始時(shí)間

若活動(dòng)ai在邊<Vj,Vk>上,則e(i)是頂點(diǎn)Vj最早時(shí)間。事件Vj發(fā)生，表明以Vj為終點(diǎn)的活動(dòng)全部結(jié)束。所以，以Vj為起點(diǎn)的所有活動(dòng)ai可以立即開始。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10e(i)=Ve(j)…………..(1)jai10謝謝觀賞2019-8-21e(i):活動(dòng)ai的最早可能開始時(shí)間若活動(dòng)aiVl(k)：事件Vk的最遲發(fā)生時(shí)間是在保證匯點(diǎn)Vn在Ve(n)時(shí)刻完成的前提下，事件Vk的允許的最遲開始時(shí)間。在不推遲工期的情況下，一個(gè)事件最遲發(fā)生時(shí)間Vl(k)應(yīng)該等于匯點(diǎn)的最早發(fā)生時(shí)間Ve(n)減去從Vk到Vn的最大路徑長(zhǎng)度。還有什么含義？以vk為終點(diǎn)的活動(dòng)的最遲完成時(shí)間。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=2a3=14a4=10Ve(n)：582240244658Ve(4)：22Vl(4)：32＝58－26261282011謝謝觀賞2019-8-21Vl(k)：事件Vk的最遲發(fā)生時(shí)間是在保證匯點(diǎn)Vn在Ve(nL(i)

：活動(dòng)ai的最遲允許開始時(shí)間

是指在不會(huì)引起工期延誤的前提下，活動(dòng)ai允許的最遲開始時(shí)間。因?yàn)槭录k發(fā)生表明以Vk為終點(diǎn)的入邊所表示的所有活動(dòng)均已完成，所以事件Vk的最遲發(fā)生時(shí)間Vl(k)也是所有以Vk為終點(diǎn)的入邊<Vj,Vk>所表示的活動(dòng)ai可以最遲完成時(shí)間。顯然，為不推遲工期，活動(dòng)ai的最遲開始時(shí)間Ll(i)應(yīng)該是ai的最遲完成時(shí)間Vl(k)減去ai的持續(xù)時(shí)間，即l(i)=Vl(k)-ACT[j][k]…………..(2)

其中,ACT[j][k]是活動(dòng)ai的持續(xù)時(shí)間（<Vj,Vk>上的權(quán)）。VkaiVj12謝謝觀賞2019-8-21L(i)：活動(dòng)ai的最遲允許開始時(shí)間L(i)-e(i)表示活動(dòng)ai的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。關(guān)鍵路徑上的活動(dòng)都滿足：l(i)=e(i)…………..(3)l(i)=e(i)表示活動(dòng)是沒有時(shí)間余量的關(guān)鍵活動(dòng)。由上述分析知，為找出關(guān)鍵活動(dòng)，需要求各個(gè)活動(dòng)的e(i)與l(i)，以判別一個(gè)活動(dòng)ai是否滿足l(i)=e(i)。Ve(k)和Vl(k)可由拓?fù)渑判蛩惴ǖ玫?。e(i)：

e(i)＝Ve(j)l(i)：

l(i)=Vl(k)-ACT[j][k]⑤時(shí)間余量l(i)-e(i)jaikaikj13謝謝觀賞2019-8-21L(i)-e(i)表示活動(dòng)ai的最早可能開始時(shí)間和最遲思考：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?分析：在AOE網(wǎng)絡(luò)中,有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑(CriticalPath)。14謝謝觀賞2019-8-21思考：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?14關(guān)鍵路徑與關(guān)鍵活動(dòng)復(fù)習(xí)關(guān)鍵路徑概念：完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長(zhǎng)度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng)，即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。關(guān)鍵活動(dòng)概念：那些滿足l(i)=e(i)的活動(dòng)ai關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此，只要找到了關(guān)鍵活動(dòng)，就可以找到關(guān)鍵路徑.15謝謝觀賞2019-8-21關(guān)鍵路徑與關(guān)鍵活動(dòng)復(fù)習(xí)關(guān)鍵路徑概念：完成工程的最短時(shí)間是從源基本思路：拓?fù)渑判?并求出Ve(k)，逆拓?fù)渑判?，求Vl(k)根據(jù)公式和權(quán)值鄰接矩陣ACT[N][N]求e（i），l（i）根據(jù)e（i），l（i）求出關(guān)鍵活動(dòng)根據(jù)關(guān)鍵活動(dòng)求出關(guān)鍵路徑1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1016謝謝觀賞2019-8-21基本思路：拓?fù)渑判?并求出Ve(k)，1324a1=8a數(shù)據(jù)結(jié)構(gòu)：AOE圖typedefstructnode{ intadjvex; intdur; structnode*next;}edgenode;//邊表結(jié)點(diǎn)typedefstruct{ vextypevertex; //頂點(diǎn)標(biāo)識(shí)

intid; //入度

edgenode*link; //指向出邊表}vexnode; //頂點(diǎn)表結(jié)點(diǎn)vexnodedig[n]; //AoE網(wǎng)數(shù)據(jù)表示1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1017謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)：AOE圖typedefstructnode13數(shù)據(jù)結(jié)構(gòu)：Ve，Vl，e，l數(shù)組intvl[n],ve[n]; intl[maxsize],e[maxsize];拓?fù)洌宏?duì)列：

tpord[n]；intfront=-1,rear=-1;18謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)：Ve，Vl，e，l數(shù)組18謝謝觀賞2019-8-2初始化voidcriticalpath(vexnodedig[]){ inti,j,k,m; intfront=-1,rear=-1; //用隊(duì)列。順序隊(duì)列的首尾指針初值

inttpord[n],vl[n],ve[n]; intl[maxsize],e[maxsize]; edgenode*p; for(i=0;i<n;i++)初始化，建立入度為0的隊(duì)列。{ ve[i]=0; if(dig[i].id==0) tpord[++rear]=i; m=0;} //計(jì)數(shù)拓?fù)渑判虻捻旤c(diǎn)數(shù)19謝謝觀賞2019-8-21初始化voidcriticalpath(vexnodeStep1:求Ve(k)

從源點(diǎn)V1出發(fā)，令Ve(1)=0，按拓?fù)湫蛄写涡蚯蟪銎溆喔黜旤c(diǎn)事件的最早發(fā)生時(shí)間:Ve(k)=max{Ve(j)+ACT[j][k]}j∈T

其中T是以頂點(diǎn)Vk為尾的所有邊的頂點(diǎn)集合(2≤k≤n)

如果網(wǎng)中有回路，不能求出關(guān)鍵路徑則算法中止；否則轉(zhuǎn)Step2。jkj2jnj1TVe(j)ACT[j][k]….….…模型方法jkjnwhile(p)//遍歷j的所有出邊{k=p->adjvex;dig[k].id--;if(ve[j]+p->dur>ve[k]) ve[k]=ve[j]+p->dur;if(dig[k].id==0) tpord[++rear]=k;p=p->next;}20謝謝觀賞2019-8-21Step1:求Ve(k)從源點(diǎn)V1出發(fā)，令Ve(求ve[k] while(front!=rear)//棧非空循環(huán),拓?fù)漤樞虮闅vAOE求Ve[j] { front++;j=tpord[front]; m++; p=dig[j].link; while(p)//遍歷j的所有出邊，修改ve[k] { k=p->adjvex; dig[k].id--; if(ve[j]+p->dur>ve[k]) ve[k]=ve[j]+p->dur; if(dig[k].id==0) tpord[++rear]=k; p=p->next; } } if(m<n) printf("\nthenetworkhasacycle\n");21謝謝觀賞2019-8-21求ve[k] while(front!=rear)//棧非正拓?fù)漤樞?？?duì)列變化？最后的front,rear值？1324a1=4a2=125678a10=12a9=6a8=8a5=18a6=8a7=6a3=14a4=1022謝謝觀賞2019-8-21正拓?fù)漤樞?？?duì)列變化？1324a1=4a2=125678a1求Ve(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Ve(k)0123456746465778320128224028365834876521tpord12225836402880464623謝謝觀賞2019-8-21求Ve(k)1324a1=8a2=125678a10=12aStep2(回退階段)：從匯點(diǎn)Vn出發(fā)，令Vl(n)=Ve(n)，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最晚發(fā)生時(shí)間：Vl(j)=min{Vl(k)-ACT[j][k]}k∈S

其中S是以頂點(diǎn)Vj為頭的所有邊的尾頂點(diǎn)的集合(2≤j≤n-1)逆序的潛在條件jkknk2k1ACT[j][k]S模型while(p)//遍歷j的所有出邊(j,k),改vl[j]{k=p->adjvex;if(vl[k]-p->dur<vl[j]) vl[j]=vl[k]-p->dur;if(dig[k].id==0) tpord[++rear]=k;p=p->next;}24謝謝觀賞2019-8-21Step2(回退階段)：從匯點(diǎn)Vn出發(fā)，令Vl(n)=V求Vl[k] for(i=0;i<n;i++) vl[i]=ve[n-1]; //vl初值 for(i=n-2;i>=0;i--) //逆拓?fù)湫蛄腥〗Y(jié)點(diǎn)

{ j=tpord[i]; p=dig[j].link; while(p) //遍歷頂點(diǎn)j的所有出邊(j,k)，修改vl[j] { k=p->adjvex; if(vl[k]-p->dur<vl[j]) vl[j]=vl[k]-p->dur; p=p->next; } }25謝謝觀賞2019-8-21求Vl[k] for(i=0;i<n;i++) vl[i]58求Vl(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Vl(k)5858585858585812345678令“-”=0080706050403020114428610486651876712812382585858585858585834876521tpord46383212804638408032124026謝謝觀賞2019-8-2158求Vl(k)1324a1=8a2=125678a10=1Step3：求每一項(xiàng)活動(dòng)ai的最早開始時(shí)間:e(i)=Ve(j)最晚開始時(shí)間:l(i)=Vl(k)-ACT[j][k]若某條邊滿足e(i)=l(i)，則它是關(guān)鍵活動(dòng)。為了簡(jiǎn)化算法,可以在求關(guān)鍵路徑之前已經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)拓?fù)渑判?并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號(hào)。不是任意一個(gè)關(guān)鍵活動(dòng)的加速一定能使整個(gè)工程提前。想使整個(gè)工程提前，要考慮各個(gè)關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。27謝謝觀賞2019-8-21Step3：求每一項(xiàng)活動(dòng)ai的最早開始時(shí)間:e(i)=求e[i],l[i],關(guān)鍵活動(dòng)l[i]-e[i]i=0;for(j=0;j<n;j++) { p=dig[j].link; while(p) //遍歷一個(gè)頂點(diǎn)的所有出邊，修改ve[k] { k=p->adjvex; //<vj,vk> e[i++]=ve[j]; //邊的序號(hào)是按操作順序排的

l[i]=vl[k]-p->dur;printf("%d\t%d\t%d\t%d\t%d\t%d\t",dig[j].vertex,dig[k].vertex,e[i],l[i],l[i]-e[i]); if(e[i]==l[i]) printf("關(guān)鍵活動(dòng)\n"); p=p->next; }}28謝謝觀賞2019-8-21求e[i],l[i],關(guān)鍵活動(dòng)l[i]-e[i]i=0;28求：e[i],l[i],l[i]-e[i]1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=7Ve(k)1222584640288012345678令“-”=0182726152413120146465778320128224028(38)465829謝謝觀賞2019-8-21求：e[i],l[i],l[i]-e[i]1324a1=8a數(shù)據(jù)結(jié)構(gòu)與算法分析第六章關(guān)鍵路徑（5）30謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)與算法分析第六章關(guān)鍵路徑（5）1謝謝觀賞2019-6.7關(guān)鍵路徑如何建立一個(gè)工程進(jìn)度控制模型？如何估算完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?人們用AOE網(wǎng)解決這個(gè)問題31謝謝觀賞2019-8-216.7關(guān)鍵路徑如何建立一個(gè)工程進(jìn)度控制模型？如何估算完成整AOE網(wǎng)（ActivityOnEdgeNetwork）在帶權(quán)的有向圖中，用結(jié)點(diǎn)表示事件：所有入邊上進(jìn)行的活動(dòng)均已完成的事件用邊表示活動(dòng)：起始結(jié)點(diǎn)事件發(fā)生后所開展的活動(dòng)邊的上權(quán)表示活動(dòng)的開銷（如持續(xù)時(shí)間）則稱此有向圖為“邊表示活動(dòng)的網(wǎng)絡(luò)”,簡(jiǎn)稱AOE網(wǎng)。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1032謝謝觀賞2019-8-21AOE網(wǎng)（ActivityOnEdgeNetwork）AOE網(wǎng)的性質(zhì)活動(dòng)開始時(shí)間：只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊代表的活動(dòng)才能開始;事件發(fā)生時(shí)間：只有在進(jìn)入某一頂點(diǎn)的各有向邊代表的活動(dòng)已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生；表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無環(huán)的，并且存在唯一的入度為0的開始頂點(diǎn)（源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（匯點(diǎn)）。33謝謝觀賞2019-8-21AOE網(wǎng)的性質(zhì)活動(dòng)開始時(shí)間：只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后AOE網(wǎng)研究的主要問題：

如果用AOE網(wǎng)表示一項(xiàng)工程，那么僅僅考慮各個(gè)子工程之間的優(yōu)先關(guān)系還不夠，更多地是關(guān)心整個(gè)工程完成的最短時(shí)間是多少，哪些活動(dòng)的延遲將影響整個(gè)工程進(jìn)度,而加速這些活動(dòng)能否提高整個(gè)工程的效率,因此AOE網(wǎng)有待研究的問題是:(1)完成整個(gè)工程至少需要多少時(shí)間？(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？34謝謝觀賞2019-8-21AOE網(wǎng)研究的主要問題：如果用AOE網(wǎng)表示一項(xiàng)工路徑長(zhǎng)度、關(guān)鍵路徑、關(guān)鍵活動(dòng)：路徑長(zhǎng)度：是指從源點(diǎn)到匯點(diǎn)路徑上所有活動(dòng)的持續(xù)時(shí)間之和。關(guān)鍵路徑：完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長(zhǎng)度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑。一個(gè)AOE中，關(guān)鍵路徑可能不只一條。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。在關(guān)鍵路徑長(zhǎng)度的范圍內(nèi)，可以安排并行的活動(dòng)35謝謝觀賞2019-8-21路徑長(zhǎng)度、關(guān)鍵路徑、關(guān)鍵活動(dòng)：6謝謝觀賞2019-8-21舉例：奧運(yùn)會(huì)競(jìng)賽日程地點(diǎn)：主會(huì)場(chǎng)需要考慮的場(chǎng)地：中心、跑道、沙坑需要考慮的項(xiàng)目：短跑、長(zhǎng)跑、馬拉松、鉛球、跳高、跳遠(yuǎn)。。。源點(diǎn)：開幕式;終點(diǎn):閉幕式36謝謝觀賞2019-8-21舉例：奧運(yùn)會(huì)競(jìng)賽日程地點(diǎn)：主會(huì)場(chǎng)7謝謝觀賞2019-8-21術(shù)語：ve(j),vl(j),e(i),l(i),ve(j):事件vj的最早發(fā)生時(shí)間。事件用v標(biāo)識(shí)，事件的編號(hào)用括號(hào)中的數(shù)字標(biāo)識(shí)，v的下標(biāo)區(qū)分“最早”和“最晚”。vl(j):事件vj的最晚發(fā)生時(shí)間。事件用“發(fā)生”描述。e(i):活動(dòng)ai的最早開始時(shí)間。沒有v的符號(hào)就是表示活動(dòng)，括號(hào)中是活動(dòng)的編號(hào)，e表示最早開始時(shí)間，l表示最晚。l(i):活動(dòng)ai的最晚開始時(shí)間。活動(dòng)用“開始”37謝謝觀賞2019-8-21術(shù)語：ve(j),vl(j),e(i),l(i),veVe(j)：事件vj的最早發(fā)生時(shí)間Ve(j)＝從源點(diǎn)V1到頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10從源點(diǎn)到頂點(diǎn)Vj的最長(zhǎng)路徑，可以包括所有以頂點(diǎn)Vj為終點(diǎn)的全部活動(dòng)所需時(shí)間。經(jīng)過這段路徑，事件Vj才有可能發(fā)生。Ve(6)是多少？38謝謝觀賞2019-8-21Ve(j)：事件vj的最早發(fā)生時(shí)間Ve(j)＝從源點(diǎn)V1e(i):活動(dòng)ai的最早可能開始時(shí)間

若活動(dòng)ai在邊<Vj,Vk>上,則e(i)是頂點(diǎn)Vj最早時(shí)間。事件Vj發(fā)生，表明以Vj為終點(diǎn)的活動(dòng)全部結(jié)束。所以，以Vj為起點(diǎn)的所有活動(dòng)ai可以立即開始。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10e(i)=Ve(j)…………..(1)jai39謝謝觀賞2019-8-21e(i):活動(dòng)ai的最早可能開始時(shí)間若活動(dòng)aiVl(k)：事件Vk的最遲發(fā)生時(shí)間是在保證匯點(diǎn)Vn在Ve(n)時(shí)刻完成的前提下，事件Vk的允許的最遲開始時(shí)間。在不推遲工期的情況下，一個(gè)事件最遲發(fā)生時(shí)間Vl(k)應(yīng)該等于匯點(diǎn)的最早發(fā)生時(shí)間Ve(n)減去從Vk到Vn的最大路徑長(zhǎng)度。還有什么含義？以vk為終點(diǎn)的活動(dòng)的最遲完成時(shí)間。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=2a3=14a4=10Ve(n)：582240244658Ve(4)：22Vl(4)：32＝58－26261282040謝謝觀賞2019-8-21Vl(k)：事件Vk的最遲發(fā)生時(shí)間是在保證匯點(diǎn)Vn在Ve(nL(i)

：活動(dòng)ai的最遲允許開始時(shí)間

是指在不會(huì)引起工期延誤的前提下，活動(dòng)ai允許的最遲開始時(shí)間。因?yàn)槭录k發(fā)生表明以Vk為終點(diǎn)的入邊所表示的所有活動(dòng)均已完成，所以事件Vk的最遲發(fā)生時(shí)間Vl(k)也是所有以Vk為終點(diǎn)的入邊<Vj,Vk>所表示的活動(dòng)ai可以最遲完成時(shí)間。顯然，為不推遲工期，活動(dòng)ai的最遲開始時(shí)間Ll(i)應(yīng)該是ai的最遲完成時(shí)間Vl(k)減去ai的持續(xù)時(shí)間，即l(i)=Vl(k)-ACT[j][k]…………..(2)

其中,ACT[j][k]是活動(dòng)ai的持續(xù)時(shí)間（<Vj,Vk>上的權(quán)）。VkaiVj41謝謝觀賞2019-8-21L(i)：活動(dòng)ai的最遲允許開始時(shí)間L(i)-e(i)表示活動(dòng)ai的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。關(guān)鍵路徑上的活動(dòng)都滿足：l(i)=e(i)…………..(3)l(i)=e(i)表示活動(dòng)是沒有時(shí)間余量的關(guān)鍵活動(dòng)。由上述分析知，為找出關(guān)鍵活動(dòng)，需要求各個(gè)活動(dòng)的e(i)與l(i)，以判別一個(gè)活動(dòng)ai是否滿足l(i)=e(i)。Ve(k)和Vl(k)可由拓?fù)渑判蛩惴ǖ玫健(i)：

e(i)＝Ve(j)l(i)：

l(i)=Vl(k)-ACT[j][k]⑤時(shí)間余量l(i)-e(i)jaikaikj42謝謝觀賞2019-8-21L(i)-e(i)表示活動(dòng)ai的最早可能開始時(shí)間和最遲思考：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?分析：在AOE網(wǎng)絡(luò)中,有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑(CriticalPath)。43謝謝觀賞2019-8-21思考：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?14關(guān)鍵路徑與關(guān)鍵活動(dòng)復(fù)習(xí)關(guān)鍵路徑概念：完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長(zhǎng)度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng)，即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。關(guān)鍵活動(dòng)概念：那些滿足l(i)=e(i)的活動(dòng)ai關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此，只要找到了關(guān)鍵活動(dòng)，就可以找到關(guān)鍵路徑.44謝謝觀賞2019-8-21關(guān)鍵路徑與關(guān)鍵活動(dòng)復(fù)習(xí)關(guān)鍵路徑概念：完成工程的最短時(shí)間是從源基本思路：拓?fù)渑判?并求出Ve(k)，逆拓?fù)渑判?，求Vl(k)根據(jù)公式和權(quán)值鄰接矩陣ACT[N][N]求e（i），l（i）根據(jù)e（i），l（i）求出關(guān)鍵活動(dòng)根據(jù)關(guān)鍵活動(dòng)求出關(guān)鍵路徑1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1045謝謝觀賞2019-8-21基本思路：拓?fù)渑判?并求出Ve(k)，1324a1=8a數(shù)據(jù)結(jié)構(gòu)：AOE圖typedefstructnode{ intadjvex; intdur; structnode*next;}edgenode;//邊表結(jié)點(diǎn)typedefstruct{ vextypevertex; //頂點(diǎn)標(biāo)識(shí)

intid; //入度

edgenode*link; //指向出邊表}vexnode; //頂點(diǎn)表結(jié)點(diǎn)vexnodedig[n]; //AoE網(wǎng)數(shù)據(jù)表示1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1046謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)：AOE圖typedefstructnode13數(shù)據(jù)結(jié)構(gòu)：Ve，Vl，e，l數(shù)組intvl[n],ve[n]; intl[maxsize],e[maxsize];拓?fù)洌宏?duì)列：

tpord[n]；intfront=-1,rear=-1;47謝謝觀賞2019-8-21數(shù)據(jù)結(jié)構(gòu)：Ve，Vl，e，l數(shù)組18謝謝觀賞2019-8-2初始化voidcriticalpath(vexnodedig[]){ inti,j,k,m; intfront=-1,rear=-1; //用隊(duì)列。順序隊(duì)列的首尾指針初值

inttpord[n],vl[n],ve[n]; intl[maxsize],e[maxsize]; edgenode*p; for(i=0;i<n;i++)初始化，建立入度為0的隊(duì)列。{ ve[i]=0; if(dig[i].id==0) tpord[++rear]=i; m=0;} //計(jì)數(shù)拓?fù)渑判虻捻旤c(diǎn)數(shù)48謝謝觀賞2019-8-21初始化voidcriticalpath(vexnodeStep1:求Ve(k)

從源點(diǎn)V1出發(fā)，令Ve(1)=0，按拓?fù)湫蛄写涡蚯蟪銎溆喔黜旤c(diǎn)事件的最早發(fā)生時(shí)間:Ve(k)=max{Ve(j)+ACT[j][k]}j∈T

其中T是以頂點(diǎn)Vk為尾的所有邊的頂點(diǎn)集合(2≤k≤n)

如果網(wǎng)中有回路，不能求出關(guān)鍵路徑則算法中止；否則轉(zhuǎn)Step2。jkj2jnj1TVe(j)ACT[j][k]….….…模型方法jkjnwhile(p)//遍歷j的所有出邊{k=p->adjvex;dig[k].id--;if(ve[j]+p->dur>ve[k]) ve[k]=ve[j]+p->dur;if(dig[k].id==0) tpord[++rear]=k;p=p->next;}49謝謝觀賞2019-8-21Step1:求Ve(k)從源點(diǎn)V1出發(fā)，令Ve(求ve[k] while(front!=rear)//棧非空循環(huán),拓?fù)漤樞虮闅vAOE求Ve[j] { front++;j=tpord[front]; m++; p=dig[j].link; while(p)//遍歷j的所有出邊，修改ve[k] { k=p->adjvex; dig[k].id--; if(ve[j]+p->dur>ve[k]) ve[k]=ve[j]+p->dur; if(dig[k].id==0) tpord[++rear]=k; p=p->next; } } if(m<n) printf("\nthenetworkhasacycle\n");50謝謝觀賞2019-8-21求ve[k] while(front!=rear)//棧非正拓?fù)漤樞?？?duì)列變化？最后的front,rear值？1324a1=4a2=125678a10=12a9=6a8=8a5=18a6=8a7=6a3=14a4=1051謝謝觀賞2019-8-21正拓?fù)漤樞?？?duì)列變化？1324a1=4a2=125678a1求Ve(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Ve(k)0123456746465778320128224028365834876521tpord12225836402880464652謝謝觀賞2019-8-21求Ve(k)1324a1=8a2=125678a10=12aStep2(回退階段)：從匯點(diǎn)Vn出發(fā)，令Vl(n)=Ve(n)，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最晚發(fā)生時(shí)間：Vl(j)=min{Vl(k)-ACT[j][k]}k∈S

其中S是以頂點(diǎn)Vj為頭的所有邊的尾頂點(diǎn)的集合(2≤j≤n-1)逆序的潛在條件jkknk2k1ACT[j][k]S模型while(p)//遍歷j的所有出邊(j,k),改vl[j]{k=p->adjvex;if(vl[k]-p->dur<vl[j]) vl[j]=vl[k]-p->dur;if(dig[k].id==0) tpord[++rear]=k;p=p->next;}53謝謝觀賞2019-8-21Step2(回退階段)：從匯點(diǎn)Vn出發(fā)，令Vl(n)=V求Vl[k] for