拓?fù)渑判蚝完P(guān)鍵路徑

關(guān)于拓?fù)渑判蚝完P(guān)鍵路徑第一頁，共三十二頁，2022年，8月28日AOV-網(wǎng)

用頂點(diǎn)表示活動，用邊來表示活動之間的先后關(guān)系的有向圖稱為頂點(diǎn)活動網(wǎng)，簡稱AOV-網(wǎng)。例如，計算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。7.5.1拓?fù)渑判虻诙?，共三十二頁?022年，8月28日

C1

高等數(shù)學(xué)

C2

程序設(shè)計基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級語言程序設(shè)計C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計算機(jī)原理C8

課程代號課程名稱先修課程第三頁，共三十二頁，2022年，8月28日學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2第四頁，共三十二頁，2022年，8月28日在AOV網(wǎng)絡(luò)中不能出現(xiàn)回路,即環(huán)。如果出現(xiàn)了環(huán)，則意味著某項活動應(yīng)以自己作為先決條件，這是荒謬的。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。第五頁，共三十二頁，2022年，8月28日檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個頂點(diǎn)(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉Ｈ绻ㄟ^拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。第六頁，共三十二頁，2022年，8月28日如果AOV網(wǎng)絡(luò)中存在環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對學(xué)生選課工程圖進(jìn)行拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨?/p>

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第七頁，共三十二頁，2022年，8月28日拓?fù)渑判虻姆椒á?/p>

輸入AOV網(wǎng)絡(luò)。令n為頂點(diǎn)個數(shù)。 ②在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點(diǎn),并輸出之;③從圖中刪去該頂點(diǎn),同時刪去所有它發(fā)出的有向邊;④重復(fù)以上②、③步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。說明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。第八頁，共三十二頁，2022年，8月28日C0C1C4C3C2C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C4C5C1C0C3(b)輸出頂點(diǎn)C2C1C4C5C3(c)輸出頂點(diǎn)C0C2C0C4C5C1C3(d)輸出頂點(diǎn)C3第九頁，共三十二頁，2022年，8月28日C1C4C5(e)輸出頂點(diǎn)C4C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5

最后得到的拓?fù)溆行蛐蛄袨镃2,C0,C3,C4,C1,C5

。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點(diǎn)，如C2和C4，也排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿傻谑摚踩摚?022年，8月28日AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C4C3C2C5C0C1C2C30C4C50012345indegreedatafirstarc

1301031adjvexnextarc30501500150第十一頁，共三十二頁，2022年，8月28日在鄰接表中增設(shè)一個數(shù)組indegree[]，記錄各頂點(diǎn)入度。在拓?fù)渑判蚯扒?初始化入度數(shù)組。入度為零的頂點(diǎn)即無前驅(qū)頂點(diǎn)。在算法中,使用棧存放入度為零的頂點(diǎn),供選擇和輸出無前驅(qū)的頂點(diǎn)。第十二頁，共三十二頁，2022年，8月28日拓?fù)渑判蛩惴擅枋鋈缦拢喝攵葹榱愕捻旤c(diǎn)入棧;當(dāng)棧不空時,重復(fù)執(zhí)行

從頂點(diǎn)棧中退出一個頂點(diǎn),并輸出之;

從AOV網(wǎng)絡(luò)中刪去這個頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減一;

如果邊的終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)棧;

如果輸出頂點(diǎn)個數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個數(shù),則報告網(wǎng)絡(luò)中存在有向環(huán)。第十三頁，共三十二頁，2022年，8月28日拓?fù)渑判虻乃惴╲oidTopologicalSort(ALGraphG){FindInDegree(G,indegree);//初始化indegree[]InitStack(S);for(i=0;i<G.vexnum;i++)//入度為零的頂點(diǎn)

if(indegree[i]==0)Push(S,i);//進(jìn)棧

count=0;//對輸出頂點(diǎn)計數(shù)

第十四頁，共三十二頁，2022年，8月28日while(!StackEmpty(S)){

Pop(S,i);//退棧

cout<<i<<G.vertices[i].data;//輸出i號頂點(diǎn)

count++;//并計數(shù)

//掃描i號頂點(diǎn)的每個鄰接點(diǎn)

for(p=G.vertices[i].

firstarc;p;p=p->nextarc){k=p->adjvex;

if(--indegree[k]==0)//頂點(diǎn)入度減1 Push(S,k);//頂點(diǎn)的入度減至零,進(jìn)棧

}}}第十五頁，共三十二頁，2022年，8月28日7.5.2關(guān)鍵路徑一、AOE網(wǎng)如果在有向無環(huán)圖中,用有向邊表示一個工程中的活動(Activity),

用邊上權(quán)值表示活動持續(xù)時間(Duration),

用頂點(diǎn)表示事件,

則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò),簡稱AOE(ActivityOnEdges)網(wǎng)。第十六頁，共三十二頁，2022年，8月28日AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時間,應(yīng)當(dāng)加快哪些活動?第十七頁，共三十二頁，2022年，8月28日從源點(diǎn)到匯點(diǎn)的路徑可能不止一條，并且這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點(diǎn)到匯點(diǎn)的最長路徑長度,即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。第十八頁，共三十二頁，2022年，8月28日要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個工程完成的活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。因此,只要找到了關(guān)鍵活動,就可以找到關(guān)鍵路徑。例如,下圖就是一個AOE網(wǎng)。V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1第十九頁，共三十二頁，2022年，8月28日二、相關(guān)術(shù)語①

事件Vi

的最早發(fā)生時間ve(i)

是從源點(diǎn)V0

到頂點(diǎn)Vi的最長路徑長度。②

事件Vi的最遲發(fā)生時間vl(i)

在不推遲整個工程完成的前提下，事件Vi

的最遲發(fā)生時間。③

活動ai的最早開始時間

e(i)④

活動ai

的最遲開始時間

l(i)

表示在不推遲整個工程完成的前提下，活動ai最遲必須開始進(jìn)行的事件。第二十頁，共三十二頁，2022年，8月28日⑤

時間余量

l(i)–e(i)

表示活動

ai的最早可能開始時間和最遲允許開始時間的時間余量。

l(i)=e(i)的活動稱為關(guān)鍵活動。第二十一頁，共三十二頁，2022年，8月28日三、怎樣求關(guān)鍵路徑？

如何找e(i)=l(i)的關(guān)鍵活動？為找出關(guān)鍵活動,需要求各個活動的e(i)

與l(i)，以判別是否l(i)=e(i)。設(shè)活動ai由弧<Vj,Vk>表示，且活動持續(xù)時間記為dut(<j,k>),

則

e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)VjVkai第二十二頁，共三十二頁，2022年，8月28日

如何求ve(i)和vl(i)？求ve(i)的遞推公式

從

ve(0)=0開始，向前遞推

<i,j

>T,i=1,2,,n-1

T

是所有以第j個頂點(diǎn)為頭的弧的集合。例，求右圖中頂點(diǎn)V6的最早發(fā)生時間。V3V4V5V6a6=3a7=2a8=1266第二十三頁，共三十二頁，2022年，8月28日V1V2V3V4V5V6頂點(diǎn)vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1032668第二十四頁，共三十二頁，2022年，8月28日求vl(i)的遞推公式從vl(n-1)=ve(n-1)開始，反向遞推

<i,j>S,i=n-2,n-3,,0S是所有以第i個頂點(diǎn)為尾的弧的集合。

例，求右圖中頂點(diǎn)V1的最遲發(fā)生時間。V1V3V2a1=3a2=224第二十五頁，共三十二頁，2022年，8月28日V1V2V3V4V5V6頂點(diǎn)vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1042678042678第二十六頁，共三十二頁，2022年，8月28日a1a2a3a4a5a6a7a8活動ell-e011000341220253660671341V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1V1V2V3V4V5V6頂點(diǎn)vevl032668042678第二十七頁，共三十二頁，2022年，8月28日四、算法實現(xiàn)實現(xiàn)步驟：

①輸入e條弧<j,k>，建立AOE-網(wǎng)的存儲結(jié)構(gòu)；

②從源點(diǎn)v0出發(fā)，令ve[0]=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時間ve[i]（1≤i≤n-1）。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟③。

③從匯點(diǎn)vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時間vl[i]（n-2≥i≥2）；

④根據(jù)各頂點(diǎn)的ve和vl的值，求每條弧s的最早發(fā)生時間e(s)和最遲發(fā)生時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。第二十八頁，共三十二頁，2022年，8月28日

算法實現(xiàn)StatusTopologicalOrder(ALGraphG,Stack&T){

//求各頂點(diǎn)事件的最早發(fā)生時間ve（全局變量），T為拓?fù)湫蛄许旤c(diǎn)棧

FindInDegree(G,indegree)；//對各頂點(diǎn)求入度

InitStack(T)；count=0；ve[0..G.vexnum-1]=0；//初始化

while(!StackEmpty(S))//S為零入度頂點(diǎn)棧

{Pop(S,j)；push(T,j)；++count；//j號頂點(diǎn)入T棧并計數(shù)

for(p=G.vertices[j].firstarc；p；p=p→nextarc){k=p→adjvex；//對j號頂點(diǎn)的每個鄰接點(diǎn)的入度減1

if(--indegree[k]==0)push(S,k)；

if(ve[j]+*(p→info)>ve[k])ve[k]=ve[j]+*(p→info)；

}

}

if(count<G.vexnum)returnERROR；//該有向網(wǎng)有回路

elsereturnOK；

}第二十九頁，共三十二頁，2022年，8月28日StatusCriticalPath(ALGraphG){

//G為有向網(wǎng)，輸出G的各項關(guān)鍵活動

if(!TopologicalOrder(G,T)returnERROR;

vl[0.