關(guān)鍵路徑算法課件

關(guān)鍵路徑與AOV-網(wǎng)相對應(yīng)的是AOE-網(wǎng)(ActivityOnEdge)即邊表示活動的網(wǎng)。AOE-網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中，頂點表示事件(Event)，弧表示活動，權(quán)表示活動持續(xù)的時間。通常，AOE-網(wǎng)可用來估算工程的完成時間。例如，圖7.29是一個假想的有11項活動的AOE-網(wǎng)。其中有9個事件v1，v2，v3，…，v9，每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。如v1表示整個工程開始，v9表示整個工程結(jié)束，v5表示a4和a5已經(jīng)完成，a7和a8可以開始。與每個活動相聯(lián)系的數(shù)是執(zhí)行該活動所需的時間。比如，活動a1需要6天，a2需要4天等。和AOV-網(wǎng)不同，對AOE-網(wǎng)有待研究的問題是：

(1)完成整項工程至少需要多少時間?(2)哪些活動是影響工程進度的關(guān)鍵?

由于在AOE-網(wǎng)中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(這里所說的路徑長度是指路徑上各活動持續(xù)時間之和，不是路徑上弧的數(shù)目)。路徑長度最長的路徑叫做關(guān)鍵路徑(CriticalPath)。假設(shè)開始點是v1，從v1到vi的最長路徑長度叫做事件vi的最早發(fā)生時間。這個時間決定了所有以vi為尾的弧所表示的活動的最早開始時間。我們用e(i)表示活動ai的最早開始時間。還可以定義一個活動的最遲開始時間l(i)，這是在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的時間。兩者之差l(i)-e(i)意味著完成活動ai的時間余量。我們把l(i)=e(i)的活動叫做關(guān)鍵活動。顯然，關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，因此提前完成非關(guān)鍵活動并不能加快工程的進度。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的工效，縮短整個工期。由上分析可知，辨別關(guān)鍵活動就是要找e(i)=l(i)的活動。為了求得AOE-網(wǎng)中活動的e(i)和l(i)，首先求事件的最早發(fā)生時間ve(j)和最遲發(fā)生時間vl(j)。如果活動ai由弧<j,k>表示，其持續(xù)時間記為dut(<j,k>),則有如下關(guān)系：

e(i)=ve(j)(7-1)l(i)=vl(k)-dut(<j,k>)

求ve(j)和vl(j)需分兩步進行：（1）從ve(0)開始向前遞推

ve(j)=Max{ve(i)+dut(<i,j>)}i<i,j>∈T,j=1,2,3,…,n-1（7-2）其中，T是所有以第j個頂點為尾的弧的結(jié)合。（2）從vl(n-1)=ve(n-1)起向后遞推

vl(i)=Min{vl(j)–dut(<i,j>)}j<i,j>∈S,i=n-2,…,0（7-3）其中，S是所有以第i個頂點為頭的弧的集合。這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。也就是說ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時間求得之后才能確定，而vl(j-1)則必須在vj的所有后繼的最遲發(fā)生時間求得之后才能確定。因此，可以在拓撲排序的基礎(chǔ)上計算ve(j-1)和vl(j-1)。由此得到求關(guān)鍵路徑的算法：(1)輸入e條弧<j，k>，建立AOE-網(wǎng)的存儲結(jié)構(gòu)；

(2)從源點v0出發(fā)，令ve[0]=0，按拓撲有序求其余各頂點的最早發(fā)生時間ve[i](1≤i≤n-1)。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟(3)。

(3)從匯點vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl[i](n—2≥i≥2)；

(4)根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。先將拓撲排序算法7.12改寫成算法7.13，則算法7.14便為求關(guān)鍵路徑的算法。/*圖的關(guān)鍵路徑問題的算法AOE.C*/#include<stdio.h>#include<stdlib.h>#defineMAXVEX100#defineTRUE1#defineFALSE0typedefcharVertexType[MAXVEX];/*存放頂點信息的字符串*/typedeffloatAdjType;typedef

struct

ArcNode{int

adjvex;/*相鄰頂點字段*/

AdjTypeweight;

struct

ArcNode*nextarc; /*鏈字段*/}ArcNode; /*邊表中的結(jié)點*/typedef

struct

VNode{VertexTypedata; /*頂點信息*/

ArcNode*firstarc; /*邊表頭指針*/}VNode,AdjList[MAXVEX]; /*頂點表中的結(jié)點*/typedef

struct{AdjListvertices;

int

vexnum,arcnum; /*圖的頂點個數(shù)*/}ALGraph;/*求出圖中所有頂點的入度，方法是搜索整個鄰接表*/voidFindInDegree(ALGraph

G,int

inDegree[]){inti;

ArcNode*p;

for(i=0;i<G.vexnum;i++)inDegree[i]=0;/*頂點入度數(shù)組賦初值*/

for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;

while(p){inDegree[p->adjvex]++;p=p->nextarc;}}}voidmakeNewAOV(ArcNode*p,int*indegree,int&top){intk;

while(p)/*刪除以該頂點為起點的邊*/{k=p->adjvex;

indegree[k]--;

if(indegree[k]==0)/*將新的入度為零的邊入棧*/{indegree[k]=top;top=k;}p=p->nextarc;}}int

topoSort(ALGraph

G,int*topo)/*拓撲排序算法*/{ArcNode*p;

int

i,j,count=0,top=-1;

int

indegree[MAXVEX];

FindInDegree(G,indegree);/*求出圖中所有頂點的入度*/

for(i=0;i<G.vexnum;i++)

if(indegree[i]==0)//將入度為零的頂點入棧

{indegree[i]=top;top=i;}

while(top!=-1)/*棧不為空*/{j=top;top=indegree[top];/*取出當前棧頂元素*/

topo[count++]=j;/*ptopo數(shù)組存放拓撲序列*/p=G.vertices[j].firstarc;//取該元素邊表中的第一個邊結(jié)點，刪除該結(jié)點,構(gòu)造新的AOV網(wǎng)

makeNewAOV(p,indegree,top);//對indegree數(shù)組進行修改

}

if(count<G.vexnum)/*AOV網(wǎng)中存在回路*/{printf("The

aovnetworkhasacycle\n");returnFALSE;}

printf("拓撲序列為：");//輸出拓撲序列

for(i=0;i<G.vexnum;i++) printf("V%1d",topo[i]+1);printf("\n");returnTRUE;}voidinsert(ALGraph&G,int

a,int

b,floatweight)/*在表尾插入表結(jié)點*/{ArcNode*p,*temp;temp=(ArcNode*)malloc(sizeof(ArcNode));temp->adjvex=b;temp->nextarc=NULL;temp->weight=weight;p=G.vertices[a].firstarc;

if(p==NULL)

G.vertices[a].firstarc=temp;else{while(p->nextarc!=NULL)p=p->nextarc;/*找表尾*/p->nextarc=temp;}}voidmakeList(ALGraph&G)/*鄰接表的構(gòu)造*/{inti;

G.vexnum=9;

for(i=0;i<G.vexnum;i++)//給頂點指針域賦初值

G.vertices[i].firstarc=NULL;insert(G,0,1,6);insert(G,0,2,4);insert(G,0,3,5);insert(G,1,4,1);insert(G,2,4,1);insert(G,3,5,2);insert(G,4,6,9);insert(G,4,7,7);insert(G,5,7,4);insert(G,6,8,2);insert(G,7,8,4);}#defineMAXEDGE100/*MAXEDEG為邊的最大數(shù)目*/voidcountve(ALGraph

G,int*topo,AdjType*ve)/*計算各事件的最早發(fā)生時間*/{int

i,j,k;

ArcNode*p;

for(i=0;i<G.vexnum;i++)ve[i]=0;/*ee數(shù)組賦初值*/

for(k=0;k<G.vexnum;k++)/*求事件vj可能的最早發(fā)生時間ee(j)*/{i=topo[k];//k僅起控制作用

p=G.vertices[i].firstarc;

while(p!=NULL){j=p->adjvex;

if(ve[i]+p->weight>ve[j])ve[j]=ve[i]+p->weight;p=p->nextarc;}}}voidcountvl(ALGraph

G,int*topo,AdjType*ve,AdjType*vl)/*計算各事件的最遲發(fā)生時間*/{int

i,j,k;ArcNode*p;

for(i=0;i<G.vexnum;i++)//求事件vi允許的最遲發(fā)生時間vl(i)

vl[i]=ve[G.vexnum-1];/*每個事件的最遲發(fā)生時間賦初值為最生事件的最早發(fā)生時間（本例均為18）*/

for(k=G.vexnum-2;k>=0;k--)/*下標從0開始，最后一個頂點無后繼，所以減2*/{i=topo[k]; p=G.vertices[i].firstarc;

while(p!=NULL){j=p->adjvex;

if(vl[j]-p->weight<vl[i])vl[i]=vl[j]-p->weight;p=p->nextarc;}}}voidcounte_l(ALGraph

G,AdjType*ve,AdjType*vl,AdjType*ee,AdjType*el)/*計算各活動的最早發(fā)生時間和最遲發(fā)生時間，并輸出關(guān)鍵路徑*/{inti=0,j,k;ArcNode*p;

printf("關(guān)鍵路徑是：");

for(j=0;j<G.vexnum;j++)/*求活動ai的最早開始時間ee(i)及最晚開始時間el(i)*/{p=G.vertices[j].firstarc;

while(p!=NULL){k=p->adjvex;

ee[i]=ve[j];

el[i]=vl[k]-p->weight;

if(ee[i]==el[i])printf("<v%1d,v%1d>,",j+1,k+1);i++;//i表示弧的序號?；〉男蛱栕缘谝粋€頂點開始到最后一個頂點止順序編號。

p=p->nextarc;}}}int

CriticalPath(ALGraphG)/*關(guān)鍵路徑算法*/{AdjType

ve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE];

int

topo[MAXVEX];

if(topoSort(G,topo)==FALSE)/*求AOE網(wǎng)的一個拓撲序列*/returnFALSE;/*若有環(huán)則返回FALSE*/

countve(G,topo,ve);/*計算數(shù)組ve，ve存放事件可能的最早發(fā)生時間*/

countvl(G,topo,ve,vl);/*計算數(shù)組vl，vl存放事件可能的最遲發(fā)生時間*/

counte_l(G,ve,vl,ee,el);/*計算數(shù)組ee,el并輸出結(jié)果*/

printf("\n");/*數(shù)組ee存放活動的最早開始時間,數(shù)組el存放活動的最晚開始時間*/returnTRUE;}voidmain()/*主程序*/{ALGraphG;

makeList(G);

if(CriticalPath(G)==FALSE)

printf("Thereisnocriticalpath!\n");}各事件的最早發(fā)生時間數(shù)組ve變化情況k012345678i=topo[k]023514768V100000000000V210666666666V320444444444V430555555555V540055577777V650007777777V7600000016161616V870000111114141414V980000000181818各事件的最遲發(fā)生時間數(shù)組vl變化情況k76543210i=topo[k]67415320V1018181818181818180V211818181866666V321818181818181866V43181818181818788V5418181877