關(guān)鍵路徑算法ppt課件-wenkub.com
2025-05-03 06:28 本頁面
【正文】 ? 另一方面，若網(wǎng)中有幾條關(guān)鍵路徑，那么，單是提高一條關(guān)鍵路徑上的關(guān)鍵活動(dòng)的速度，還不能導(dǎo)致整個(gè)工程縮短工期，而必須提高同時(shí)在幾條關(guān)鍵路徑上的活動(dòng)的速度。實(shí)際上，求關(guān)鍵路徑的方法本身最初就是與維修和建造工程一起發(fā)展的。 ? } ?void main() /*主程序 */ ?{ ALGraph G。 /*計(jì)算數(shù)組 ve， ve存放事件可能的最早發(fā)生時(shí)間 */ ? countvl(G,topo,ve,vl)。 ? } } } ? int CriticalPath(ALGraph G) /*關(guān)鍵路徑算法 */ ? { AdjType ve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE]。 ? i++。 ? while(p!=NULL) ? { k=padjvex。 ? printf(關(guān)鍵路徑是： )。 ? if(vl[j]pweightvl[i]) vl[i]=vl[j]pweight。k=0。 ? for(i=0。 ? if(ve[i]+pweightve[j]) ve[j]=ve[i]+pweight。k。 ? for(i=0。 ? insert(G,6,8,2)。 insert(G,3,5,2)。 insert(G,0,2,4)。 ? for(i=0。 /*找表尾 */ ? pnextarc=temp。 ? tempweight=weight。G,int a,int b,float weight) ? /*在表尾插入表結(jié)點(diǎn) */ ? { ArcNode *p,*temp。i++) printf(V%1d ,topo[i]+1)。 ? return FALSE。 /* 取出當(dāng)前棧頂元素 */ ? topo[count++]=j。i++) ? if(indegree[i]==0) / / 將入度為零的頂點(diǎn)入棧 ? { indegree[i]=top。 ? int indegree[MAXVEX]。 ? top=k。top) ? { int k。i++) ? { p=[i].firstarc。i。 /* 圖的頂點(diǎn)個(gè)數(shù) */ ? }ALGraph。 /* 頂點(diǎn)信息 */ ? ArcNode *firstarc。 /* 相鄰頂點(diǎn)字段 */ ? AdjType weight。 ?先將拓?fù)渑判蛩惴? ，則算法。 ?由此得到求關(guān)鍵路徑的算法： ? (1)輸入 e條弧 j， k，建立 AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)； ? (2)從源點(diǎn) v0出發(fā)，令 ve[0]=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間 ve[i] (1≤i≤n1)。 ? （ 2）從 vl(n1)=ve(n1)起向后遞推 ? vl(i) = Min{ vl (j) – dut(i,j) } ? j ? i,j ∈ S , i=n2,…,0 （ 73） ? 其中， S是所有以第 i個(gè)頂點(diǎn)為頭的弧的集合。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的工效，縮短整個(gè)工期。還可以定義一個(gè)活動(dòng)的最遲開始時(shí)間 l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始進(jìn)行的時(shí)間。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑 (Critical Path
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1