圖與網(wǎng)絡(luò)ppt課件(編輯修改稿)
2025-06-08 07:51 本頁面
【文章內(nèi)容簡介】 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3(2) v6 (4) (4) [9] [∞] [∞] 7 最短路算法 (6) v2,v4為剛得到 P標(biāo)號的點 ,考察 弧 (v2,v5)，(v4,v5)， (v4,v6)的端點 v5,v6 T(v5)=min{T(v5), P(v4)+ ω45, P(v2)+ ω25} =min{∞,4+3,4+4}=7 T(v6)=min{T(v6), P(v4)+ ω46}=min{9,4+4}=8 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) [8] [7] [∞] 7 v3(2) v6 最短路算法 (7) 比較所有 T標(biāo)號， T(v5)最小， 所以令 P(v5) =7 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) [∞] [8] v3(2) v6 7 最短路算法 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) [14] [8] v3(2) v6 (8) v5為剛得到 P標(biāo)號的點，考察弧 (v5,v6)，(v5,v7)的端點 v6,v7 T(v6)=min{T(v6), P(v5)+ ω56}=min{8,7+1}=8 T(v7)=min{T(v7), P(v5)+ ω57}=min{∞,7+7}=14 7 最短路算法 (9) 比較所有 T標(biāo)號， T(v6)最小，所以令 P(v6)=8 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) [14] (8) v3(2) v6 7 最短路算法 (10) v6為剛得到 P標(biāo)號的點，考察 弧 (v6,v7)的端點 v7 T(v7)=min{T(v7), P(v6)+ ω67}=min{14,8+5}=13 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) [13] (8) v3(2) v6 7 最短路算法 (11) 只有一個 T標(biāo)號 T(v7)，令 P(v7)=13 ，停止。 ? ? ? ? ? ? ? v1 (0) v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 (4) (4) (7) (13) (8) v3(2) v6 7 計算結(jié)果見上圖， v1到 v7的最短路為： 76431 vvvvv ????765431 vvvvvv ?????同時得到 v1到其余各點的最短路。 應(yīng)用舉例 ? 例： (設(shè)備更新問題 ) 某企業(yè)在四年內(nèi)都要使用某種設(shè)備，在每年年初作出是購買新設(shè)備
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1