物流運(yùn)輸路徑規(guī)劃-資料下載頁
2025-02-18 03:54本頁面
【正文】 +∞∞ +∞∞+∞∞（ 1）首先給 v1以 P標(biāo)號(hào) ，P(v1)＝ 0，給其余所有點(diǎn)T標(biāo)號(hào)， T(vj)＝＋ ∞ （ j = 2， 3， … 6)(0) P標(biāo)號(hào)以 （ ） 形式標(biāo)在結(jié)點(diǎn)旁邊， T標(biāo)號(hào)以不帶（）的數(shù)字標(biāo)在結(jié)點(diǎn)旁邊 .v6v5v3v1v4v2365112436二、最短路問題的算法二、最短路問題的算法 P(v2 )= 3 （ 3）5P(v3 )= 4 （ 4）+∞∞+∞∞v6v5v3v1v4v2365112436+∞∞+∞∞+∞∞(0)9（ 2）考察 v1: T(v2)=min [T(v2)， P(v1) +a12] ＝ min [∞ ， 0＋ 3] = 3T(v3)=min [T(v3)， P(v1) +a13]＝ min [∞ ， 0＋ 5] = 5所以， P(v2 )= 3（ 3）考察 v2:T(v3)=min [T(v3)， P(v2) +a23]＝ min [5， 3＋ 1] = 4T(v4)=min [T(v4)， P(v2) +a24]＝ min [∞ ， 3＋ 6] = 9所以， P(v3)=4T(v3 )= 5 T(v4)= 9 二、最短路問題的算法二、最短路問題的算法 P(v5)= 5（ 3）（ 4）v6v5v3v1v4v2365112436+∞∞+∞∞(0)9（ 5）T(v4)= 8 （ 4）考察 v3: T(v5)=min [T(v5)， P(v3) +a35]＝ min [∞ ， 4＋ 1] = 5T(v4)=min [T(v4)， P(v3) +a34]＝ min [9， 4＋ 4] = 8所以， P(v5)= 5（ 5）考察 v5:T(v6)=min [T(v6)， P(v5) +a56]＝ min [∞ ， 5＋ 6] = 11T(v4)=min [T(v4)， P(v5) +a54]＝ min [8， 5＋ 2] = 7所以， P(v4)= 7 8T(v6)= 11 11（ 7）P( 7二、最短路問題的算法二、最短路問題的算法 （ 3）（ 4）v6v5v3v1v4v236511243611(0)（ 5）（ 7）（ 6）考察 v4:T(v6)=min [T(v6)， P(v4) +a46]＝ min [11， 7＋ 3] = 10所以， P(v6)= 10所有點(diǎn)都 標(biāo) 上 P 標(biāo) 號(hào)． P(v6)= 10 (10)(7) 標(biāo)出最短路 v1到 v6的最短路 可從 v1開始，根據(jù)永久性標(biāo)號(hào)數(shù)值回溯得到．(7) 標(biāo)出最短路 最短路徑是： v1→ v2→ v3→ v5→ v4→ v6 ，路長 10．同 時(shí)得到，到其余各點(diǎn)的最短路，即各點(diǎn)的永久性標(biāo)號(hào) P（ vi）． 注意： 雙標(biāo)號(hào)法只適用于所有 wij ≥0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，則算法失效． （ 3）（ 4）v6v5v3v1v4v2365112436(0)（ 5）（ 7）(10)二、最短路問題的算法二、最短路問題的算法 謝謝觀看 /歡迎下載BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1