關(guān)鍵路徑算法ppt課件(存儲(chǔ)版)
【正文】 c。 /*數(shù)組 ee存放活動(dòng)的最早開始時(shí)間 ,數(shù)組 el存放活動(dòng)的最晚開始時(shí)間 */ ? return TRUE。只有在不改變網(wǎng)的關(guān)鍵路徑的情況下，提高關(guān)鍵活動(dòng)的速度才有效。但是，由于網(wǎng)中各項(xiàng)活動(dòng)是互相牽涉的，因此，影響關(guān)鍵活動(dòng)的因素亦是多方面的，任何一項(xiàng)活動(dòng)持續(xù)時(shí)間的改變都會(huì)影響關(guān)鍵路徑的改變。 /*計(jì)算數(shù)組 vl， vl存放事件可能的最遲發(fā)生時(shí)間 */ ? counte_l(G,ve,vl,ee,el)。 //i表示弧的序號(hào)。 ? for(j=0。k) /*下標(biāo)從 0開始，最后一個(gè)頂點(diǎn)無后繼，所以減 2*/ ? { i=topo[k]。 ? p=pnextarc。i。 ? insert(G,4,6,9)。i。 ? p=[a].firstarc。 printf(\n)。 /*ptopo數(shù)組存放拓?fù)湫蛄?*/ ? p=[j].firstarc。 ? FindInDegree(G,indegree)。 ? while(p) /* 刪除以該頂點(diǎn)為起點(diǎn)的邊 */ ? { k=padjvex。i++) inDegree[i]=0。 /* 邊表頭指針 */ ? }VNode,AdjList[MAXVEX]。 ? /*圖的關(guān)鍵路徑問題的算法 */ ? include ? include ? define MAXVEX 100 ? define TRUE 1 ? define FALSE 0 ? typedef char VertexType[MAXVEX]。 ? 這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。兩者之差 l(i)e(i)意味著完成活動(dòng) ai的時(shí)間余量。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間。 AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件 (Event)，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間。路徑長度最長的路徑叫做關(guān)鍵路徑 (Critical Path)。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的工效，縮短整個(gè)工期。 ?由此得到求關(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)。 /* 相鄰頂點(diǎn)字段 */ ? AdjType weight。 /* 圖的頂點(diǎn)個(gè)數(shù) */ ? }ALGraph。i++) ? { p=[i].firstarc。 ? top=k。i++) ? if(indegree[i]==0) / / 將入度為零的頂點(diǎn)入棧 ? { indegree[i]=top。 ? return FALSE。G,int a,int b,float weight) ? /*在表尾插入表結(jié)點(diǎn) */ ? { ArcNode *p,*temp。 /*找表尾 */ ? pnextarc=temp。 insert(G,0,2,4)。 ? insert(G,6,8,2)。k。 ? for(i=0。 ? if(vl[j]pweightvl[i]) vl[i]=vl[j]pweight。 ? while(p!=NULL) ? { k=padjvex。 ? } } } ? int CriticalPath(ALGraph G) /*關(guān)鍵路徑算法 */ ? {
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1