運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)(編輯修改稿)
2024-08-28 15:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 、什么是最短路問(wèn)題 例：求下圖中 v1到 v8的最短距離 第三節(jié) 最短路問(wèn)題 v1 v2 v3 v4 v5 v7 v6 v8 3 5 6 1 1 7 4 2 3 5 2 1 6 5 9 第三節(jié) 最短路問(wèn)題 基本思想： 從 vs出發(fā)，逐步向外探尋最短路。執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)（稱為這個(gè)點(diǎn)的標(biāo)號(hào)），它或者表示從 vs到該點(diǎn)的最短路的權(quán)（稱為P標(biāo)號(hào)）、或者是從 vs到該點(diǎn)的最短路的權(quán)的上界（稱為 T標(biāo)號(hào)），方法的每一步是去修改 T標(biāo)號(hào)，并且把某一個(gè)具有 T標(biāo)號(hào)的點(diǎn)改變?yōu)榫?P標(biāo)號(hào)的點(diǎn)。從而使D中具有 P標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)，這樣，至少經(jīng)過(guò) P1步，就可以求出從 vs到各點(diǎn)的最短路。 二、狄克斯拉（ Dijkstra）算法 第三節(jié) 最短路問(wèn)題 (1)給 vs以 P標(biāo)號(hào)， P(vs)=0,其余各點(diǎn)均給 T標(biāo)號(hào)，T(vj)=+∞ 。 (2)若 vi點(diǎn)為剛得到 P標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn) vj: (vi,vj)屬于 E，且 vj為 T標(biāo)號(hào)。對(duì) vj的 T標(biāo)號(hào)進(jìn)行如下的更改： T(vj)=min[T(vj)， P(vi)+wij] (3)比較所有具有 T標(biāo)號(hào)的點(diǎn)，把最小者改為 P標(biāo)號(hào)，即： P(vi’)=min[T(vi)] 當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為 P標(biāo)號(hào)。若全部點(diǎn)均為 P標(biāo)號(hào)則停止。否則用 vi’代 vi轉(zhuǎn)回（ 2）。 步驟： GO T(v2)=min{+∞ ， 0+3}=3， k(v2)=v1 T(v3)=min{+∞ ， 0+5}=5， k(v3)=v1 T(v4)=min{+∞ ， 0+6}=6， k(v4)=v1 將具有最小 T標(biāo)號(hào)的 v2點(diǎn)改為 P標(biāo)號(hào)：P(v2)=3 T(v3)=min{5， 3+1}=4， k(v3)=v2 T(v5)=min{+∞ ， 3+7}=10， k(v5)=v2 T(v6)=min{+∞ ， 3+4}=7， k(v6)=v2 解：標(biāo) p(v1)=0，其余點(diǎn)標(biāo) T(vi)=+∞ ，(i=2,3,4,5,6,7,8) v1 v2 v3 v4 v5 v7 v6 v8 3 5 6 1 1 7 4 2 3 5 2 1 6 5 9 0 3 將具有最小 T標(biāo)號(hào)的 v3點(diǎn)改為 P標(biāo)號(hào)： P(v3)=4 v1 v2 v3 v4 v5 v7 v6 v8 3 5 6 1 1 7 4 2 3 5 2 1 6 5 9 0 3 T(v4)=min{6， 4+1}=5， k(v4)=v3 T(v6)=min{7， 4+2}=6， k(v6)=v3 將具有最小 T標(biāo)號(hào)的 v4點(diǎn)改為 P標(biāo)號(hào)： P(v4)=5 T(v6)=min{6， 5+3}=6 T(v7)=min{+∞ ， 5+5}=10， k(v7)=v4 4 5 T(V3)=4 T(V4)=6 T(V5)=10 T(V6)=7 T(V7)=+∞ T(V8)=+∞ v1 v2 v3 v4 v5 v7 v6 v8 3 5 6 1 1 7 4 2 3 5 2 1 6 5 9 0 3 4 5 將具有最小 T標(biāo)號(hào)的 v6點(diǎn)改為 P標(biāo)號(hào)： P(v6)=6 T(v5)=min{10， 6+2}=8， k(v5)=v6 T(v7)=min{10， 6+1}=7， k(v7)=v6 T(v8)=min{+∞ ， 6+9}=15， k(v8)=v6 6 將具有最小 T標(biāo)號(hào)的 v7點(diǎn)改為 P標(biāo)號(hào)： P(v7)=7 T(v8)=min{15， 7+5}=12， k(v8)=v7 7 T(V5)=10 T(V6)=6 T(V7)=10 T(V8)=+∞ v1 v2 v3 v4 v5 v7 v6 v8 3 5 6 1 1 7 4 2 3 5 2 1 6 5 9 0 3 4 5 6 7 將具有最小 T標(biāo)號(hào)的 v5點(diǎn)改為 P標(biāo)號(hào)： P(v5)=8 8 T(v8)=min{12， 8+6}=12 將具有最小 T標(biāo)號(hào)的 v8點(diǎn)改為 P標(biāo)號(hào)： P(v8)=12 12 ∴ 最短路徑為 v1→ v2→ v3→ v6→ v7→ v8；最短距離為 12。 T(V5)=8 T(V8)=12 第三節(jié) 最短路問(wèn)題 V1 V2 V5 V3 V6 V4 V7 9 8 5 1 2 8 7 2 3 3 4 4 例：用狄式算法 v1點(diǎn)到 v7點(diǎn)的最短路 第三節(jié) 最短路問(wèn)題 例：求下圖 G中任意兩點(diǎn)間的最短路。 v1 v2 v3 v4 v5 5 3 10 2 2 1 2 6 2 4 4 8 第三節(jié) 最短路問(wèn)題 三、 Floyd算法 適用： 求網(wǎng)絡(luò)網(wǎng)中任意兩點(diǎn)間的最短路。 步驟： （ 1）輸入權(quán)矩陣 D(0)=D； （ 2）計(jì)算 D(k)=(dij(k))n n (k=1,2,…,n) 其中 dij(k)=min[dij(k1),dik(k1)+dkj(k1)] （ 3） D(n)=(dij(n)) n n中元素 dij(n)就是 vi到 vj的最短路長(zhǎng)。 第三節(jié) 最短路問(wèn)題 ??????????????????????0442406282032210052150)0
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1