有向圖最長路徑

1、有向圖最長路徑的求解拓撲排序法1問題我們通常把程序流程、生產(chǎn)過程、施工工程等都視為一個工程。工程通常分為若干個稱為“活動”的子工程。完成了這些子工程，總的工程隨即完成。而在實際操作中，我們往往把某一工程的抽象為一個有向的帶權(quán)的無環(huán)圖。其中節(jié)點即代表其事件，邊表示“活動”，權(quán)表示持續(xù)的時間。由于網(wǎng)圖中的有些過程可以并行進行，以致于由始點到終點的路徑可能不止一條，路徑的長度也可能不同，于是完成不同路徑所需的時間也便不同。但只有各條路徑上的所有活動都完成了，這個工程才算完成。因此，求出網(wǎng)圖中最長路徑就顯得有了它的現(xiàn)實意義。的提出2任務(wù)要求將有向圖輸入到程序計算有向圖最長路徑路線及長度輸出計算結(jié)果即軟

2、件結(jié)構(gòu)3程序結(jié)構(gòu)開始判斷是否有回環(huán)結(jié)束反向計算各節(jié)點最早開始時間判斷各節(jié)點是否為關(guān)鍵節(jié)點輸出最長路徑及其長度輸入節(jié)點數(shù)/邊數(shù)輸入各邊信息將有向圖信息存為鄰接表前向計算各節(jié)點最晚開始時間NY4數(shù)據(jù)結(jié)構(gòu)使用兩種結(jié)構(gòu)體表征各節(jié)點及各邊屬性。typedef struct line /邊結(jié)構(gòu)體 int nodeclose; /該邊指向節(jié)點 int weight; /該邊權(quán)重 struct line *next; /此節(jié)點下一 /出邊地址line;typedef struct /節(jié)點結(jié)構(gòu)體 int nodeid; /節(jié)點序號 int getin; /節(jié)點入度 line *last; /最后一條出邊地址ea

3、chnode5數(shù)據(jù)結(jié)構(gòu)邊頭為1的邊邊尾序號邊權(quán)重下條邊頭為1的邊邊頭為1的邊邊尾序號邊權(quán)重下條邊頭為1的邊邊頭為1的邊邊尾序號邊權(quán)重下條邊頭為1的邊.節(jié)點1序號入度末出邊地址節(jié)點2節(jié)點3節(jié)點4節(jié)點N6算法轉(zhuǎn)換輸入信息循環(huán)節(jié)點數(shù)次輸入邊頭邊尾邊權(quán)重將邊尾序號賦值給臨時結(jié)構(gòu)體將邊權(quán)重賦值給臨時結(jié)構(gòu)體將該邊頭點結(jié)構(gòu)體原指向邊地址同仁給臨時結(jié)構(gòu)體將臨時結(jié)構(gòu)體地址賦值給邊頭結(jié)構(gòu)體中鄰接邊7算法計算節(jié)點最晚開始時間循環(huán)節(jié)點數(shù)次遍歷該節(jié)點的所有出邊使出邊的尾點的最晚開始時間為原有值與出邊加邊權(quán)重中的較大者8算法計算節(jié)點最早開始時間循環(huán)節(jié)點數(shù)-1次依計算節(jié)點最晚開始時間時的堆棧順序遍歷該節(jié)點的所有入邊使節(jié)點的最早開始時間為原有最早時間與(該點所有出邊的尾點的最早開始時間-邊重)的較小值9算法計算最長路徑循環(huán)節(jié)點數(shù)次計算該點最早開始時間及最晚開始時間的差值=0?YN該點為最長路徑上的點該點不是最長路徑上的點10測試計算如下所示有向圖的最長路徑。1425987103622224444333451