關(guān)鍵路徑算法ppt課件-在線瀏覽
2025-06-23 06:28本頁面
【正文】 動(dòng)的 e(i)和 l(i)， 首先求事件的最早發(fā)生時(shí)間 ve(j)和最遲發(fā)生時(shí)間 vl(j)。 ? （ 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)為頭的弧的集合。也就是說 ve(j1)必須在 vj的所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，而 vl(j1)則必須在 vj的所有后繼的最遲發(fā)生時(shí)間求得之后才能確定。 ?由此得到求關(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)。 ? (3)從匯點(diǎn) vn出發(fā)，令 vl[n1]=ve[n1]，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間 vl[i](n—2≥i≥2)； ? (4)根據(jù)各頂點(diǎn)的 ve和 vl值，求每條弧 s的最早開始時(shí)間 e(s)和最遲開始時(shí)間 l(s)。 ?先將拓?fù)渑判蛩惴? ，則算法。 /*存放頂點(diǎn)信息的字符串 */ ? typedef float AdjType。 /* 相鄰頂點(diǎn)字段 */ ? AdjType weight。 /* 鏈字段 */ ? }ArcNode。 /* 頂點(diǎn)信息 */ ? ArcNode *firstarc。 /* 頂點(diǎn)表中的結(jié)點(diǎn) */ ? typedef struct ? { AdjList vertices。 /* 圖的頂點(diǎn)個(gè)數(shù) */ ? }ALGraph。 ? ArcNode *p。i。 /*頂點(diǎn)入度數(shù)組賦初值 */ ? for(i=0。i++) ? { p=[i].firstarc。 ? p=pnextarc。top) ? { int k。 ? indegree[k]。 ? top=k。 ? } ? } ? int topoSort(ALGraph G,int *topo) /*拓?fù)渑判蛩惴?*/ ? { ArcNode *p。 ? int indegree[MAXVEX]。 /* 求出圖中所有頂點(diǎn)的入度 */ ? for(i=0。i++) ? if(indegree[i]==0) / / 將入度為零的頂點(diǎn)入棧 ? { indegree[i]=top。 ? } ? while(top!=1) /* 棧不為空 */ ? { j=top。 /* 取出當(dāng)前棧頂元素 */ ? topo[count++]=j。 ? //取該元素邊表中的第一個(gè)邊結(jié)點(diǎn)，刪除該結(jié)點(diǎn) ,構(gòu)造新的 AOV網(wǎng) ? makeNewAOV(p,indegree,top)。 ? return FALSE。 //輸出拓?fù)湫蛄? ? for(i=0。i++) printf(V%1d ,topo[i]+1)。 ? return TRUE。G,int a,int b,float weight) ? /*在表尾插入表結(jié)點(diǎn) */ ? { ArcNode *p,*temp。 ? tempadjvex=b。 ? tempweight=weight。 ? if(p==NULL
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1