離散數(shù)學(xué)ch04圖論最短路徑與關(guān)鍵路徑-wenkub.com
2025-01-15 02:22 本頁(yè)面
【正文】 ( ) 6 4 2 。( ) m i n{ 6 2 , 11 4 , 6 4 } 2 。( ) m i n{ 12 6 } 6 。T E vT E vT E vT E v?? ? ?? ? ? ?? ? ? ?5678( ) m a x{ 1 3 , 4 4 } 8 。 最短路徑及關(guān)鍵路徑 解 ： 各 點(diǎn) 最 早 完 成時(shí) 間 用 公 式 (7a) 計(jì) 算 ：3412( ) 0 。 最短路徑及關(guān)鍵路徑 關(guān)鍵路徑問(wèn)題 —— PERT圖（計(jì)劃評(píng)審技術(shù)圖） , ,D V E Vv? ???定 義 ： 設(shè) 為 一 個(gè) 有 向 圖 稱(chēng){ | }( ,)D xv x V v x E?? ? ? ? ? ??v為 的 后 繼 元 集 ；{ | }( ,)D xv x V x v E?? ? ? ? ? ??v為 的 先 驅(qū) 元 集 . 最短路徑及關(guān)鍵路徑 關(guān)鍵路徑問(wèn)題 —— PERT圖（計(jì)劃評(píng)審技術(shù)圖） ,D V E W n? ? ?設(shè) 是 一 個(gè) 階 有 向 帶 權(quán) 圖 ， 滿 足( 1 )( 2 )( 3 ) 0 ,0(4 ,)i j ijDDvwv??是 簡(jiǎn) 單 圖 ；中 無(wú) 回 路 ；有 一 個(gè) 頂 點(diǎn) 入 度 為 稱(chēng) 此 頂 點(diǎn) 為 始 點(diǎn) ； 有 一 個(gè) 頂 點(diǎn) 出 度 為 ， 稱(chēng) 此 頂 點(diǎn) 為 終 點(diǎn) ；記 邊 帶 的 ， 它 一 般權(quán) 為 表 示 時(shí) 間 ；P ER TD則 稱(chēng) 為 圖 . 最短路徑及關(guān)鍵路徑 關(guān)鍵路徑問(wèn)題 —— PERT圖（計(jì)劃評(píng)審技術(shù)圖） 在 PERT圖中求關(guān)鍵路徑，就是從始點(diǎn)到終點(diǎn)的一條最長(zhǎng)路徑，通過(guò)求各頂點(diǎn)的最早完成時(shí)間來(lái) 求關(guān)鍵路徑。 【 例 】 試求無(wú)向賦權(quán)圖中 v1到 v6的最短路徑。 最短路徑及關(guān)鍵路徑 Dijkstras基本思路： ?Step1: 初始化：將 v1置為 P標(biāo)號(hào)， d(v1)=0， P={v1}， ?vi(i≠1) 置vi 為 T標(biāo)號(hào)，即 T=VP，且 d(vi)=W(v1, vi) 若 viadjvi d(vi)=∞ else 最短路徑及關(guān)鍵路徑 ?Step2:找最小 尋找具有最小值的 T標(biāo)號(hào)的結(jié)點(diǎn)。 最短路徑及關(guān)鍵路徑 將頂點(diǎn)集 V分成兩部分，一部分成為具有 P（永久性）標(biāo)號(hào)的集合，另一部分成為具有 T（暫時(shí)性）標(biāo)號(hào)的集合。 下一條路徑長(zhǎng)度 次短的最短路徑 的特點(diǎn)： 路徑長(zhǎng)度最短的 最短路徑 的特點(diǎn)： 它只可能
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1