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