《圖與網(wǎng)絡(luò)》ppt課件-預(yù)覽頁
【正文】 ] [∞] [∞] 7 最短路算法 ? ? ? ? ? ? ? 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 ，停止。這種設(shè)備在四年之內(nèi)每年年初的價格以及使用不同時間（年）的設(shè)備的維修費用估計為： 年份 1 2 3 4 年初購價 10 11 12 13 維修費用 2 4 7 14 應(yīng)用舉例 ? 問題：制定一個四年之內(nèi)的設(shè)備更新計劃，使得四年之內(nèi)的設(shè)備購置費和維修費用之和最小。 ? 當(dāng) fij=cij,則稱流對邊（ vi,vj）是飽和的。 ? 增廣鏈： 從發(fā)點到收點的鏈，前向弧的流量小于容量，后向弧的流量大于零。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1