圖論模型：最短路ppt課件(編輯修改稿)
2025-06-02 23:19 本頁面
【文章內(nèi)容簡介】 {})(),(m i n {)( 14144 ??????? fvPvTvT:,P)6( 4241211 vvvvvvv 的端點(diǎn)標(biāo)號的點(diǎn)，考察邊為剛得到9)(T 6 ?v282671951368431V0V1V3V2V4V5V7V6 。3)(P)(TT)7( 44 ?vv 最小，所以令標(biāo)號，比較所有:,,P)8( 7527454244 vvvvvvvvvv 的端點(diǎn)考察邊標(biāo)號的點(diǎn)為剛得到。6)(P)(TT)9( 55 ?vv 最小，所以令標(biāo)號，比較所有8}53,8m i n {})(),(m i n {)( 42422 ????? fvPvTvT6}33,m i n {})(),(m i n {)( 45455 ??????? fvPvTvT11}83,m i n {})(),(m i n {)( 47477 ??????? fvPvTvT9)( 6 ?vT:,P)10(7627565255vvvvvvvvvv 的端點(diǎn)標(biāo)號的點(diǎn)，考察邊為剛得到 。7)(P)(TT)11( 22 ?vv 最小，所以令標(biāo)號，比較所有7}16,8m i n {})(),(m i n {)( 52522 ????? fvPvTvT10}46,10m i n {})(),(m i n {)( 56566 ????? fvPvTvT11}66,11m i n {})(),(m i n {)( 57577 ????? fvPvTvT:,P)12( 6622 vvvv 的端點(diǎn)考察邊標(biāo)號的點(diǎn)為剛得到9}27,10m i n {})(),(m i n {)( 26266 ????? fvPvTvT11)( 7 ?vT11}39,11m i n {})(),(m i n {)( )13( 67677 ????? fvPvTvT11)( 7 ?? vP 9)( 6 ?? vP 迭代次數(shù) T(v0) T(v1) T(v2) T(v3) T(v4) T(v5) T(v6) T(v7) P標(biāo)號 1 0 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 2 0 2 8 1 +∞ +∞ +∞ +∞ v0 3 2 8 1 +∞ +∞ +∞ +∞ v3 4 2 8 +∞ +∞ 10 +∞ v1 5 8 3 +∞ 10 +∞ V4 6 8 6 10 11 V5 7 7 10 11 V2 8 9 11 V6 9 11 V7 最短路權(quán) 0 2 7 1 3 6 9 11 父點(diǎn) v0 v0 v5 v0 v1 v4 V2 v4 2211381V0V1V3V2V4V5V7V6 ? 例 2(設(shè)備更新問題 )某企業(yè)使用一種設(shè)備 ,每年年初 ,企業(yè)都要作出決定 ,如果要繼續(xù)使用舊的 , 。若購買一臺新設(shè)備 ,要付購買費(fèi) .使制定一個 5年更新計(jì)劃 ,使總費(fèi)用最少 ? ? 已知設(shè)備每年年初的購買費(fèi)分別為 :11,11,12,12,13,使用不同時間設(shè)備所需的維修費(fèi)為 : ? 解：設(shè) bi表示設(shè)備在第 i年年初的購買費(fèi)， ci表示設(shè)備使用 i年后的維修費(fèi)，把這個問題化為求有向賦權(quán)圖G=（ V,E,F）中的最短路問題。 設(shè)備年齡 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1