關(guān)鍵路徑算法ppt課件(已改無錯(cuò)字)
2023-06-06 06:28:56 本頁面
【正文】 初值 */ ? for(k=0。k。k++) /* 求事件 vj可能的最早發(fā)生時(shí)間 ee(j) */ ? { i=topo[k]。 //k僅起控制作用 ? p=[i].firstarc。 ? while(p!=NULL) ? { j=padjvex。 ? if(ve[i]+pweightve[j]) ve[j]=ve[i]+pweight。 ? p=pnextarc。 ? } ? } ? } ? void countvl(ALGraph G,int *topo,AdjType *ve, AdjType *vl) /*計(jì)算各事件的最遲發(fā)生時(shí)間 */ ? { int i,j,k。 ArcNode *p。 ? for(i=0。i。i++) //求事件 vi允許的最遲發(fā)生時(shí)間 vl(i) ? vl[i]=ve[]。 /*每個(gè)事件的最遲發(fā)生時(shí)間賦初值為最生事件的最早發(fā)生時(shí)間（本例均為 18） */ ? for(k=。k=0。k) /*下標(biāo)從 0開始，最后一個(gè)頂點(diǎn)無后繼，所以減 2*/ ? { i=topo[k]。 ? p=[i].firstarc。 ? while(p!=NULL) ? { j=padjvex。 ? if(vl[j]pweightvl[i]) vl[i]=vl[j]pweight。 ? p=pnextarc。 ? } ? } ? } ? void counte_l(ALGraph G,AdjType *ve,AdjType *vl,AdjType *ee,AdjType *el) ? /*計(jì)算各活動(dòng)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，并輸出關(guān)鍵路徑 */ ? { int i=0,j,k。 ArcNode *p。 ? printf(關(guān)鍵路徑是： )。 ? for(j=0。j。j++) /*求活動(dòng) ai的最早開始時(shí)間 ee(i)及最晚開始時(shí)間 el(i) */ ? { p=[j].firstarc。 ? while(p!=NULL) ? { k=padjvex。 ? ee[i]=ve[j]。 ? el[i]=vl[k]pweight。 ? if(ee[i]==el[i]) printf(v%1d, v%1d, ,j+1,k+1)。 ? i++。 //i表示弧的序號(hào)?；〉男蛱?hào)自第一個(gè)頂點(diǎn)開始到最后一個(gè)頂點(diǎn)止順序編號(hào)。 ? p=pnextarc。 ? } } } ? int CriticalPath(ALGraph G) /*關(guān)鍵路徑算法 */ ? { AdjType ve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE]。 ? int topo[MAXVEX]。 ? if(topoSort(G,topo)==FALSE) /*求 AOE網(wǎng)的一個(gè)拓?fù)湫蛄?*/ ? return FALSE。 /*若有環(huán)則返回 FALSE*/ ? countve(G,topo,ve)。 /*計(jì)算數(shù)組 ve， ve存放事件可能的最早發(fā)生時(shí)間 */ ? countvl(G,topo,ve,vl)。 /*計(jì)算數(shù)組 vl， vl存放事件可能的最遲發(fā)生時(shí)間 */ ? counte_l(G,ve,vl,ee,el)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1