現(xiàn)代物流運(yùn)輸管理第八章運(yùn)輸方案設(shè)計(jì)(編輯修改稿)
2025-01-20 08:04 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 最少 。 ? 數(shù)學(xué)模型 —— 求網(wǎng)絡(luò)圖中二點(diǎn)之間的最短路問(wèn)題 。 采用網(wǎng)絡(luò)規(guī)劃中求最短路 Dijkstra算法 （ 標(biāo)號(hào)算法 ） 。 ? 狄克拉斯 (Dijkstra)算法 本算法由 Dijkstra在 1959年提出，可用于求解指定兩點(diǎn)間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路。目前被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好方法。算法思路基于以下原理： 此算法采用標(biāo)號(hào)法，可用兩種標(biāo)號(hào)： T標(biāo)號(hào)(試探性 )與 P標(biāo)號(hào) (永久性 )。給 vi點(diǎn)一個(gè) P表示從 vs到 vi點(diǎn)的最短路權(quán)， vi點(diǎn)的標(biāo)號(hào)不再改變。給 vi點(diǎn)一個(gè) T標(biāo)號(hào)時(shí)，表示從 vs到 vi的估計(jì)最短路的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒(méi)有得到 P標(biāo)號(hào)的都有 T標(biāo)號(hào) 步驟： （ 1）給 v1以 P標(biāo)號(hào)， P(v1)=0，其余各點(diǎn)均給 T標(biāo)號(hào)， T(vi)=+∞ （ 2）設(shè) vj是剛剛得到的 P標(biāo)號(hào)點(diǎn)，考慮所有從 Vi出發(fā)到達(dá)的且仍是 T標(biāo)號(hào)的點(diǎn) vj，將這些 T標(biāo)號(hào)改為 ； （ 3）比較所有具有 T標(biāo)號(hào)的點(diǎn)，把最小者改為 P標(biāo)號(hào)，即 ( ) m in[ ( ) , ( ) ]j j i ijT v T v P v l??( ) m in[ ( ) ]iiP v T v?當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為 P標(biāo)號(hào)。若全部點(diǎn)均為 P標(biāo)號(hào)時(shí)，則停止，否則 轉(zhuǎn)回（ 2） iv 用 Dijkstra算法求 v1到 v8的最短路。 v2 v1 v4 v6 v3 v5 v7 v8 4 4 4 6 7 5 6 9 5 1 4 7 5 P(v1)=0 T(v5)=∞ T(v2)=∞ 4 4 4 6 7 5 6 9 5 1 4 7 5 T(v4)=∞ T(v6)=∞ T(v3)=∞ T(v7)=∞ T(v8)=∞ 第一步： T(v2)=∞ P(v1)=0 4 4 4 6 7 5 6 9 5 1 4 7 5 T(v4)=∞ T(v6)=∞ T(v3)=∞ T(v5)=∞ T(v7)=∞ T(v8)=∞ 第二步： 2 2 1 12( ) m in[ ( ) , ( ) ] m in[ , 0 4] 4v T v P v l? ? ? ? ? ? ?3 3 1 13( ) m in[ ( ) , ( ) ] m in[ , 0 6] 6T v T v P v l? ? ? ? ? ? ?P )=4 )=6 比較所有 T標(biāo)號(hào)， T(v2) 最小 =4,于是令 P (v2)=T(v2)=4的并記錄相應(yīng)路徑 P(v1)=0 4 4 4 6 7 5 6 9 5 1 4 7 5 T(v4)=∞ T(v6)=∞ T(v5)=∞ T(v7)=∞ T(v8)=∞ 第三步： 4 4 2 24( ) m in[ ( ) , ( ) ] m in[ , 4 5 ] 9T v T v P v l? ? ? ? ? ? ?5 5 2 25( ) in[ ( ) , ( ) ] m in[ , 4 4] 8v T v P v l? ? ? ? ? ?P(v2)=4 T(v3)=6 )=8 )=9 比
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1