最短路徑問題-數(shù)學(xué)建模

1、Floyd算法Dijkstra算法兩個例子的求解引例2：最廉價(jià)航費(fèi)表的制定引例1：最短運(yùn)輸路線問題最短路徑問題的0-1規(guī)劃模型3102374116598140504025105001520251501020402010010252520100551025255505l定義：設(shè)定義：設(shè)P(u,v)是加權(quán)圖是加權(quán)圖G中從中從u到到v的路徑的路徑,則該路則該路徑上的邊權(quán)之和稱為該路徑的權(quán)徑上的邊權(quán)之和稱為該路徑的權(quán),記為記為w(P). 從從u到到v的路徑中權(quán)最小者的路徑中權(quán)最小者 P*(u,v)稱為稱為u到到v的最短路徑的最短路徑.10237411659811023741165981算法步驟算法步驟

2、S: 具有永久標(biāo)號的頂點(diǎn)集具有永久標(biāo)號的頂點(diǎn)集;l(v): v的標(biāo)記的標(biāo)記; f(v):v的父頂點(diǎn)的父頂點(diǎn),用以確定最短路徑用以確定最短路徑; 輸入加權(quán)圖的帶權(quán)鄰接矩陣輸入加權(quán)圖的帶權(quán)鄰接矩陣w=w(vi,vj)nxm.1)初始化初始化 令令l(v0)=0,S= ; v v0 ,l(v)= ;2)更新更新l(v), f(v) 尋找不在尋找不在S中的頂點(diǎn)中的頂點(diǎn)u,使使l(u)為最小為最小.把把u加入到加入到S中中,然后對所有不在然后對所有不在S中的頂點(diǎn)中的頂點(diǎn)v,如如l(v)l(u)+w(u,v),則則更新更新l(v),f(v), 即即 l(v)l(u)+w(u,v),f(v)u;3)重復(fù)步驟

3、重復(fù)步驟2), 直到所有頂點(diǎn)都在直到所有頂點(diǎn)都在S中為止中為止.91023741165981算法步驟算法步驟 d(i,j) : i到到j(luò)的距離的距離; path(i,j): i到到j(luò)的路徑上的路徑上i的后繼點(diǎn)的后繼點(diǎn); 輸入帶權(quán)鄰接矩陣輸入帶權(quán)鄰接矩陣a(i,j).1）賦初值）賦初值 對所有對所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新）更新d(i,j) , path(i,j) 對所有對所有i,j, 若若d(i,k)+d(k,j)d(i,j),則則 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13）重復(fù)）重

4、復(fù)2)直到直到k=n+11314102374116598115運(yùn)行上頁程序輸出：運(yùn)行上頁程序輸出：dis = 21path = 1 8 9 10 11 因此頂點(diǎn)因此頂點(diǎn)1到頂點(diǎn)到頂點(diǎn)11的最短路徑為的最短路徑為18 9 10 11, 其長度為其長度為21。1605040251050015202515010204020100102525201005510252555005040251050015202515010204020100102525201005510252555018 假設(shè)圖有假設(shè)圖有 n 個頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)個頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)到頂點(diǎn)n的的最短路徑最短路徑.最短路徑問題的

5、最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 設(shè)決策變量為設(shè)決策變量為xij , 當(dāng)頂點(diǎn)當(dāng)頂點(diǎn)1至頂點(diǎn)至頂點(diǎn)n的路上含弧的路上含弧(i,j) 時(shí)，時(shí)，xij=1；否則；否則xij=0. 其數(shù)學(xué)規(guī)劃表達(dá)式為其數(shù)學(xué)規(guī)劃表達(dá)式為( , )11( , )( , )min ; 1,1,. . 1, ; 0,1, . 01,( , ). ijiji jEnnijjijji jEj iEijw xistxxininxi jE 或19最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 例例 （有向圖最短路問題）（有向圖最短路問題） 在下圖中，用點(diǎn)表示城市，現(xiàn)在下圖中，用點(diǎn)表示城市，現(xiàn)有有 共共7個城市個城

6、市.點(diǎn)與點(diǎn)之間的連線表示城市間有道點(diǎn)與點(diǎn)之間的連線表示城市間有道路相連路相連.連線旁的數(shù)字表示道路的長度連線旁的數(shù)字表示道路的長度.現(xiàn)計(jì)劃從城市現(xiàn)計(jì)劃從城市 到城市到城市 鋪設(shè)一條天然氣管道，請?jiān)O(shè)計(jì)出最小價(jià)格管道鋪設(shè)方案鋪設(shè)一條天然氣管道，請?jiān)O(shè)計(jì)出最小價(jià)格管道鋪設(shè)方案. 12123, ,AB B C C C DAD本質(zhì)是求從城市本質(zhì)是求從城市 到城市到城市 的一條最短路的一條最短路AD20最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 解：解：寫出相應(yīng)的寫出相應(yīng)的LINGO程序，程序，MODEL: 1! We have a network of 7 cities. We want t

7、o find 2 the length of the shortest route from city 1 to city 7; 3 4sets: 5 ! Here is our primitive set of seven cities; 6 cities/A, B1, B2, C1, C2, C3, D/; 7 8 ! The Derived set roads lists the roads that 9 exist between the cities; 21最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 10 roads(cities, cities)/ 11 A,B1 A

8、,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/: w, x; 13 endsets 14 15 data: 16 ! Here are the distances that correspond 17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19 enddata 22最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 20 21 n=size(cities); ! The number of cities; 22 min=sum(roads: w*x); 23 for

9、(cities(i) | i #ne# 1 #and# i #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25 sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END23最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 在上述程序中，在上述程序中， 21句中的句中的n=size(cities)是計(jì)算集是計(jì)算集cities的個數(shù)，這里的計(jì)算結(jié)果是的個數(shù)，這里的計(jì)算結(jié)果是 , 這樣編寫方法目的這樣編寫方法目的在于提高程序的通用性在于提高程序的通用性.22句表示目標(biāo)函數(shù)句表示目標(biāo)函數(shù), 即求道路

10、的最即求道路的最小權(quán)值小權(quán)值.23, 24句表示約束中句表示約束中 的情況，即最短路中的情況，即最短路中中間點(diǎn)的約束條件中間點(diǎn)的約束條件.25句表示約束中句表示約束中 的情況，即最短的情況，即最短路中起點(diǎn)的約束路中起點(diǎn)的約束.7n 1,iin1i 約束中約束中 的情況，也就是最短路中終點(diǎn)的情況，沒的情況，也就是最短路中終點(diǎn)的情況，沒有列在程序中，因?yàn)榻K點(diǎn)的約束方程與前個方程相關(guān)有列在程序中，因?yàn)榻K點(diǎn)的約束方程與前個方程相關(guān).當(dāng)然，如果你將此方程列入到當(dāng)然，如果你將此方程列入到LINGO程序中，計(jì)算時(shí)程序中，計(jì)算時(shí)也不會出現(xiàn)任何問題，因?yàn)橐膊粫霈F(xiàn)任何問題，因?yàn)長INGO軟件可以自動刪除軟件可以

11、自動刪除描述線性規(guī)劃可行解中的多余方程描述線性規(guī)劃可行解中的多余方程.in24最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 LINGO軟件計(jì)算結(jié)果（僅保留非零變量）如下軟件計(jì)算結(jié)果（僅保留非零變量）如下Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路是即最短

12、路是 , 最短路長為最短路長為6個單位個單位.11ABCD25最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 例例（無向圖的最短路問題）求下圖中（無向圖的最短路問題）求下圖中 到到 的最短路的最短路.1v11v 本例是處理無向圖的最短路問題，在處理方式上與有向圖本例是處理無向圖的最短路問題，在處理方式上與有向圖的最短路有一些差別的最短路有一些差別.26最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 解：解： 對于無向圖的最短路問題，可以這樣理解，從點(diǎn)對于無向圖的最短路問題，可以這樣理解，從點(diǎn) 到點(diǎn)到點(diǎn) 和點(diǎn)和點(diǎn) 到點(diǎn)到點(diǎn) 的邊看成有向弧，其他各條邊均看成有的邊看成有向弧，其

13、他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路問題來編程序，但按照這種方法編寫問題來編程序，但按照這種方法編寫LINGO程序相當(dāng)于邊程序相當(dāng)于邊（弧）增加了一倍（?。┰黾恿艘槐?這里選擇鄰接矩陣和賦權(quán)矩陣的方法編寫這里選擇鄰接矩陣和賦權(quán)矩陣的方法編寫LINGO程序程序.1viviv11vMODEL: 1 sets: 2 cities/1.11/; 3 roads(cities, cities): p, w, x; 4 endsets 27最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 5 data: 6 p =

14、 0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0 11 0 0 1 0 1 0 1 0 1 0 0 12 0 0 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;28最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型

15、 17 w = 0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0 3 0 4 0 6 0 0 23 0 0 2 9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0; 28 enddata29最短路徑問題的

16、最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 29n=size(cities); 30min=sum(roads:w*x); 31for(cities(i) | i #ne# 1 #and# i #ne# n: 32 sum(cities(j): p(i,j)*x(i,j) 33 =sum(cities(j): p(j,i)*x(j,i); 34sum(cities(j): p(1,j)*x(1,j)=1; END30最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 在上述程序中在上述程序中，第，第6行到第行到第16行給出了圖的鄰接矩陣行給出了圖的鄰接矩陣 ， 到到 和和 到到 的邊按單

17、向計(jì)算，其余邊雙的邊按單向計(jì)算，其余邊雙向計(jì)算向計(jì)算.第第17行到第行到第27行給出了圖的賦權(quán)矩陣行給出了圖的賦權(quán)矩陣 , 注意：由注意：由于有了鄰接矩陣于有了鄰接矩陣 ，兩點(diǎn)無道路連接時(shí)，權(quán)值可以定義為，兩點(diǎn)無道路連接時(shí)，權(quán)值可以定義為0. 其它的處理方法基本上與有向圖相同其它的處理方法基本上與有向圖相同.P1v234,vvv8910,vvv11vWP用用LINGO軟件求解，得到（僅保留非零變量）軟件求解，得到（僅保留非零變量） Global optimal solution found at iteration: 2 0 Objective value: 13.00000 31最短路徑問題的最短路徑問題的0-10-1規(guī)劃模型規(guī)劃模型 Variable Value