關鍵路徑求解

《關鍵路徑求解》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、數(shù)據(jù)結構中關鍵路徑算法的實現(xiàn)與應用摘?要?介紹求關鍵路經(jīng)的算法，對于給出的事件結點網(wǎng)絡，要求求出從起點到終點的所有路徑，經(jīng)分析、比較后找出長讀最大的路徑，從而得出求關鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。關鍵詞?關鍵路徑最少時間1：引言通常把計劃、施工過程、生產流程、程序流程的都當成一個工程。除了很小的工程外、一般都把工程分為若干個叫做“活動”的子工程。完成了這些“活動”的子工程，這個工程就可以完成了。通常我們用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊表示活動Vi必須先于活動Vj進行。如果在無有向環(huán)的帶權有向

2、圖中用有向邊表示一個工程中的各項活動（ACTIVITY），用有向邊上的權值表示活動的持續(xù)時間（DURATION），用頂點表示事件（EVENT），則這種的有向圖叫做用邊表示活動的網(wǎng)絡，簡稱AOE（activeonedges）網(wǎng)絡。???AOE網(wǎng)絡在某些工程估算方面非常有用。他可以使人們了解：????????（1）：研究某個工程至少需要多少時間？????????（2）：那些活動是影響工程進度的關鍵？在AOE網(wǎng)絡中，有些活動可以并行的進行。從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然

3、不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度就叫做關鍵路徑（criticalpath）。2：設計步驟：　　　　1:以某一工程為藍本，采用圖的結構表示實際的工程計劃的時間?！　　　?:調查以分析和預測這個工程計劃個階段的時間?！　　???????3:用調查的結果建立ＡＯE網(wǎng)（ActivityOnEdgeNetwork），即邊表示活動的網(wǎng)絡，并用圖的形式表示。4:用圖來存儲這些信息。???????5:用CreateGraphic

4、();函數(shù)建立AOE圖。???????6:用SearchMapPath();函數(shù)求出最大路徑，并打印出關鍵路徑。???????7:編寫代碼???????8:測試3:設計代碼：#include#include#include#include//#definePROJECTNUMBER?9//10//#definePLANNUMBER11//13typedefstructnode{??????intadjvex;??????intdut;??????structnode*

5、next;}edgenode;typedefstruct{??????int?projectname;??????int?id;??????edgenode*link;}vexnode;//vexnodeGraphicmap[PROJECTNUMBER];voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber){??????intbegin,end,duttem;??????edgenode*p;??????for(inti=0;i

6、+)??????{???????Graphicmap[i].projectname=i;????????????Graphicmap[i].id=0;????????????Graphicmap[i].link=NULL;??????}??????????printf("某項目的開始到結束在圖中的節(jié)點輸入");??????printf("如：3,4,9回車表示第三節(jié)點到第四節(jié)點之間的活動用了9個單位時間");??????for(intk=0;k

7、canf("%d,%d,%d",&begin,&end,&duttem);????????????p=(edgenode*)malloc(sizeof(edgenode));????????????p->adjvex=end-1;?????????????p->dut=duttem;????????????Graphicmap[end-1].id++;????????????p->next=Graphicmap[begin-1].link;????????????Graphicmap[begin-1].link=p;??????}}intSearc

8、hMapPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,