【正文】 定義下列幾個參數(shù)。[j]從源點v1到vj的最長路徑長度叫做事件vj的最早發(fā)生時間。這個時間決定了所有以vj為尾的弧表示的活動的最早開始時間?？捎孟旅孢f推公式計算ve[j]: ve[l]=0 ve[j]=max{ve[i]+dut(vi,vj)}vi,vj∈T其中，T是所有以vj為頭的弧的集合，dut(vi,vj)為弧vi,vj上的權(quán)。[i]vl[i]是指在不推遲整個工期的前提下(即保證事件vn在ve(n)時刻發(fā)生的前提下),事件vi允許的最晚發(fā)生時間。等于ve(n)減去vi到vn的最長路徑長度。 vl[n]=ve[n] vl[i]=min{vl[j]dut(vi,vj)} vi,vj∈S其中S是所有以vi為尾的弧的集合。[k]若活動ak是由弧vi,vj表示，只有事件vi發(fā)生了，活動ak才能開始。所以，活動ak的最早開始時間應(yīng)等于事件vi的最早發(fā)生時間。ee[k]=el[i][k]在不推遲整個工程完成的前提下，活動ak最遲必須開始進(jìn)行的時間稱為活動ak的最遲開始時間。若由弧vi,vj表示活動ak，則ak的最遲開始時間等于事件vj的最遲發(fā)生時間vl[j]減去活動ak的持續(xù)時間。即： el[k]=vl[j]dut(vi,vj)把el[k]=ee[k]的活動ak稱為關(guān)鍵活動。el[i]ee[i]表示完成活動ak的時間余量，即在不延遲工期的前提下活動ak可以延遲的時間。求關(guān)鍵路徑的算法步驟為：(1)輸入e條弧j,k，建立AOE網(wǎng)的存儲結(jié)構(gòu)。(2)從源點v0出發(fā)，令ve[0]=0,按拓?fù)溆行蚯笃溆喔黜旤c的最早發(fā)生時間ve[i](1≤i≤n1)。如果得到的拓?fù)溆行蛐蛄兄许旤c個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止：否則執(zhí)行步驟(3).(3)從匯點vn出發(fā)，令vl[n1]=ve[n1],按逆拓?fù)溆行蚯笃溆喔黜旤c的最遲發(fā)生時間vl[i](n2≥i≥2)。(4)根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間ee(s)和最遲開始時間el(s)。若某條弧滿足條件ee(s)=el(s),則為關(guān)鍵活動。用頭結(jié)點中增加一個存儲相應(yīng)頂點的入度值域的特殊鄰接表作AOE網(wǎng)的存儲結(jié)構(gòu)，求關(guān)鍵路徑的算法如下：int ve[MAXVEX],vl[MAXVEX]。int tporder(ALGraph G,SqStack *T) { SqStack s。 int i,v,k,count=0。 ArcNode *p。 InitStack(s)。 for(i=1。i=。i++) [i].indegree=0。 for(i=1。i=。i++) { p=[i].firstarc。 while(p) { [padjvex].indegree++。 p=pnext。 } } for(i=1。i=。i++) { ve[i]=0。 if(![i].indegree) Push(s,i)。 } while(!StackEmpty(s)) { Pop(s,v)。 count++。 Push(T,v)。 for(p=[v].firstarc。p。p=pnext) { k=padjvex。 [k].indegree。 if(![k].indegree) Push(s,k)。 if(ve[v]+pwve[k]) ve[k]=ve[v]+pw。 } } return count。}void KeyPath(ALGraph G){ int j,k,v,dut,ee,el。 ArcNode *p。 SqStack T。 InitStack(T)。 if(tporder(G,amp。T)!=) cout該網(wǎng)有回路！。 for(v=1。v=。v++) vl[v]=ve[]。 while(!StackEmpty(T)) { Pop(T,j)。 for(p=[j].firstarc。p。p=pnext) { k=padjvex。 dut=pw。 if(vl[k]dutvl[j]) vl[j]=vl[k]dut。 } } for(j=1。j=。j++) for(p=[j].firstarc。p。p=pnext) { k=padjvex。 dut=pw。 ee=ve[j]。 el=vl[k]dut。 if(ee==el) printf(%d,%d,%d,%d,%d\n,j,k,dut,ee,el)。 printf([%c,%c]\n,[j].data,[k].data)。 }}算法運行結(jié)果如下圖所示：設(shè)AOE網(wǎng)中有n個事件，e個活動，則求關(guān)鍵路徑的時間復(fù)雜度為O(n+e)。*******************************************************************void CreatDNG_M(MGraph amp。G){ int i,j,c,w。 cout請輸入頂點數(shù),邊數(shù):。 cin。 printf(請輸入頂點:)。 for(i=1。i=。i++) cin[i]。 for(i=1。i=。i++) for(j=1。j=。j++) [i][j]=MAXCOST。 printf(請輸入邊和權(quán)值:\n)。 for(c=1。c=。c++) { cinijw。 [i][j]=w。 } cout創(chuàng)建的鄰接矩陣為：endl。 for(i=1。i=。i++) { for(j=1。j=。j++) cout[i][j] 。 coutendl。 } cout鄰接矩陣創(chuàng)建完畢endl。}算法運行結(jié)果如下圖所示：void CreatDNG_ALG(ALGraph amp。G){ int i,s,d,w。 ArcNode *p。 cout請輸入頂點數(shù),邊數(shù)：。 cin。 for (i=1。i=。i++) { printf(第%d個結(jié)點信息:,i)。 cin[i].data。 [i].firstarc=NULL。 } for (i=1。i=。i++) { printf(第%d條邊=起點序號,終點序號，權(quán)值:,i)。 cinsdw。 p=(ArcNode *)malloc(sizeof(ArcNode))。 padjvex=d。 pw=w。 pnext=[s].firstarc。 /*p插入頂點s的鄰接表中*/ [s].firstarc=p。 } }算法運行結(jié)果如下圖所示：void SinMiniPathD(MGraph G,int v){ struct { int length。 int pre。 }dist[MAXVEX]。 int final[MAXVEX]。 int i,j,k,min。 SqStack s。 for(i=1。i=。i++) { final[i]=0。 dist[i].length=[v][i]。 if(dist[i].lengthMAXCOST) dist[i].pre=v。 else dist[i].pre=1。 } dist[v].pre=1。 final[v]=1。 for(i=1。i。i++) { min=MAXCOST。 for(j=1。j=。j++) if((!final[j])amp。amp。(dist[j].lengthmin)) { min=dist[j].length。 k=j。 } if(minMAXCOST) { final[k]=1。 for(j=1。j=。j++) if(!final[j]amp。amp。(min+[k][j]dist[j].length)) { dist[j].length=min+[k][j]。 dist[j].pre=k。 } else break。 } } for(i=1。i=。i++) { printf(%c%c:%d\n,[v],[i],dist[i].length)。 InitStack(s)。 Push(s,i)。 j=dist[i].pre。 while(j!=1) { Push(s,j)。 j=dist[j].pre。 } while(!StackEmpty(s)) { Pop(s,k)。 cout[k]。 } coutendl。 }}void displaypath(MGraph,int[][MAXVEX],int[][MAXVEX])。void DouMiniPathF(MGraph G){ int path[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]。 int i,j,k。 for(i=1。i=。i++) for(j=1。j=。j++) { D[i][j]=[i][j]。 path[i][j]=1。 } for(k=1。k=。k++) for(i=1。i=。i++) for(j=1。j=。j++) if(D[i][j]D[i][k]+D[k][j]) { D[i][j]=D[i][k]+D[k][j]。 path[i][j]=k。 } displaypath(G,D,path)。}void ppath(MGraph G,int path[][MAXVEX],int i,int j){ int k。 k=path[i][j]。 if(k==1)return。 ppath(G,path,i,k)。 cout[k]。 ppath(G,path,k,j)。}void displaypath(MGraph G,int D[][MAXVEX],int path[][MAXVEX]){ int i,j。 for(i=1。i=。i++) for(j=1。j=。j++) if(D[i][j]==MAXCOST) printf(%c到%c沒有路徑可達(dá),[i],[j])。 else { printf(%c到%c的最短路徑為:%c,[i],[j],[i])。 ppath(G,path,i,j)。 printf(%c\n,[j])。 printf(最短路徑為長度為：%d\n,D[i][j])。 }}int ve[MAXVEX],vl[MAXVEX]。int tporder(ALGraph G,SqStack *T) { SqStack s。 int i,v,k,count=0。 ArcNode *p。 InitStack(s)。 for(i=1。i=。i++) [i].indegree=0。 for(i=1。i=。i++) { p=[i].firstarc。 while(p) { [padjvex].indegree++。 p=pnext。 } } for(i=1。i=。i++) { ve[i]=0。 if(![i].indegree) Push(s,i)。 } while(!StackEmpty(s)) { Pop(s,v)。 count++。 Push(T,v)。 for(p=[v].firstarc。p。p=pnext) { k=padjvex。 [k].indegree。 if(![k].indegree) Push(s,k)。 if(ve[v]+pwve[k]) ve[k]=ve[v]+pw。 } } return count。}void KeyPath(ALGraph G){ int j,k,v,dut,ee,el。 ArcNode *p。 SqStack T。 InitStack(T)。 if(tporder(