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