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

最短路徑問(wèn)題數(shù)學(xué)建模GongQu1第一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三主要內(nèi)容Floyd算法Dijkstra算法兩個(gè)例子的求解引例2：最廉價(jià)航費(fèi)表的制定引例1：最短運(yùn)輸路線問(wèn)題最短路徑問(wèn)題的0-1規(guī)劃模型2第二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三如圖的交通網(wǎng)絡(luò)，每條弧上的數(shù)字代表車輛在該路段行駛所需的時(shí)間，有向邊表示單行道，無(wú)向邊表示可雙向行駛。若有一批貨物要從1號(hào)頂點(diǎn)運(yùn)往11號(hào)頂點(diǎn)，問(wèn)運(yùn)貨車應(yīng)沿哪條線路行駛，才能最快地到達(dá)目的地？

引例1：最短運(yùn)輸路線問(wèn)題

102374116598135122106158879932273第三頁(yè)，共三十一頁(yè)，編輯于2023年，星期三某公司在六個(gè)城市C1,C2,C3,C4,C5,C6都有分公司，公司成員經(jīng)常往來(lái)于它們之間，已知從Ci到Cj的直達(dá)航班票價(jià)由下述矩陣的第i行，第j列元素給出（表示無(wú)直達(dá)航班），該公司想算出一張任意兩個(gè)城市之間的最廉價(jià)路線航費(fèi)表。

引例2：最廉價(jià)航費(fèi)表的制定4第四頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題定義：設(shè)P(u,v)是加權(quán)圖G中從u到v的路徑,則該路徑上的邊權(quán)之和稱為該路徑的權(quán),記為w(P).從u到v的路徑中權(quán)最小者P*(u,v)稱為u到v的最短路徑.102374116598135122106158879932275第五頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑算法Dijkstra算法使用范圍:尋求從一固定頂點(diǎn)到其余各點(diǎn)的最短路徑;有向圖、無(wú)向圖和混合圖;權(quán)非負(fù).算法思路：采用標(biāo)號(hào)作業(yè)法,每次迭代產(chǎn)生一個(gè)永久標(biāo)號(hào),從而生長(zhǎng)一顆以v0為根的最短路樹,在這顆樹上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間的路徑皆為最短路徑.102374116598135122106158879932276第六頁(yè)，共三十一頁(yè)，編輯于2023年，星期三Dijkstra算法——算法步驟S:具有永久標(biāo)號(hào)的頂點(diǎn)集;l(v):v的標(biāo)記;f(v):v的父頂點(diǎn),用以確定最短路徑;

輸入加權(quán)圖的帶權(quán)鄰接矩陣w=[w(vi,vj)]nxm.初始化令l(v0)=0,S=;vv0,l(v)=;更新l(v),f(v)

尋找不在S中的頂點(diǎn)u,使l(u)為最小.把u加入到S中,然后對(duì)所有不在S中的頂點(diǎn)v,如l(v)>l(u)+w(u,v),則更新l(v),f(v),即l(v)l(u)+w(u,v),f(v)u;重復(fù)步驟2),直到所有頂點(diǎn)都在S中為止.7第七頁(yè)，共三十一頁(yè)，編輯于2023年，星期三MATLAB程序（Dijkstra算法）function[min,path]=dijkstra(w,start,terminal)n=size(w,1);label(start)=0;f(start)=start;fori=1:nifi~=startlabel(i)=inf;end,ends(1)=start;u=start;whilelength(s)<nfori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;iflabel(v)>(label(u)+w(u,v))label(v)=(label(u)+w(u,v));f(v)=u;end,end,endv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;ifk>label(v)k=label(v);v1=v;end,end,ends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=startpath(i+1)=f(path(i));i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);①②③8第八頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑算法Dijkstra算法程序的使用說(shuō)明：調(diào)用格式為

[min,path]=dijkstra(w,start,terminal),

其中輸入變量w為所求圖的帶權(quán)鄰接矩陣，start,terminal分別為路徑的起點(diǎn)和終點(diǎn)的號(hào)碼。返回start到terminal的最短路徑path及其長(zhǎng)度min.注意：頂點(diǎn)的編號(hào)從1開始連續(xù)編號(hào)。9第九頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑算法Floyd算法使用范圍:求每對(duì)頂點(diǎn)的最短路徑;有向圖、無(wú)向圖和混合圖;算法思想:

直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出n個(gè)矩陣D(1),D(2),…,D(n),D(n)是圖的距離矩陣,同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑.1023741165981351221061588799322710第十頁(yè)，共三十一頁(yè)，編輯于2023年，星期三Floyd算法——算法步驟

d(i,j):i到j(luò)的距離;path(i,j):i到j(luò)的路徑上i的后繼點(diǎn);

輸入帶權(quán)鄰接矩陣a(i,j).1）賦初值對(duì)所有i,j,d(i,j)a(i,j),path(i,j)j,k=l.2）更新d(i,j),path(i,j)

對(duì)所有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),kk+13）重復(fù)2)直到k=n+111第十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三MATLAB程序（Floyd算法）function[D,path,min1,path1]=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;end,end,endfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);end,end,end,endifnargin==3min1=D(start,terminal);m(1)=start;i=1;path1=[];whilepath(m(i),terminal)~=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;end12第十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑算法Floyd算法程序的使用說(shuō)明：1.[D,path]=floyd(a),返回矩陣D,path。其中a是所求圖的帶權(quán)鄰接矩陣，D(i,j)表示i到j(luò)的最短距離;path(i,j)表示i與j之間的最短路徑上頂點(diǎn)i的后繼點(diǎn).2.[D,path,min1,path1]=floyd(a,i,j)返回矩陣D,path;并返回i與j之間的最短距離min1和最短路徑path1.13第十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期三edge=[2,3,1,3,3,5,4,4,1,7,6,6,5,5,11,1,8,6,9,10,8,9,9,10;...3,4,2,7,5,3,5,11,7,6,7,5,6,11,5,8,1,9,5,11,9,8,10,9;...3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7,2,9,9,2,2];n=11;weight=inf*ones(n,n);fori=1:nweight(i,i)=0;endfori=1:size(edge,2)weight(edge(1,i),edge(2,i))=edge(3,i);end[dis,path]=dijkstra(weight,1,11)引例1的Matlab求解1023741165981351221061588799322714第十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期三運(yùn)行上頁(yè)程序輸出：dis=21path=1891011

因此頂點(diǎn)1到頂點(diǎn)11的最短路徑為1→8→9→10→11,其長(zhǎng)度為21。引例1的求解15第十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期三建立腳本m文件如下：a=[0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;…40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0];[D,path]=floyd(a)運(yùn)行便可輸出結(jié)果。引例2的Matlab求解16第十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期三運(yùn)行輸出結(jié)果：

D=035453525103501520302545150102035352010010252530201003510253525350path=165556623446523454523456143451124416D便是最廉價(jià)的航費(fèi)表，要求飛行路線，由path矩陣可以得到，比如2到5的路線：path(2,5)=4,path(4,5)=5,因此，應(yīng)為2→4→517第十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期三假設(shè)圖有n個(gè)頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)n的最短路徑.最短路徑問(wèn)題的0-1規(guī)劃模型設(shè)決策變量為xij,當(dāng)頂點(diǎn)1至頂點(diǎn)n的路上含弧(i,j)時(shí)，xij=1；否則xij=0.其數(shù)學(xué)規(guī)劃表達(dá)式為18第十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

例（有向圖最短路問(wèn)題）在下圖中，用點(diǎn)表示城市，現(xiàn)有共7個(gè)城市.點(diǎn)與點(diǎn)之間的連線表示城市間有道路相連.連線旁的數(shù)字表示道路的長(zhǎng)度.現(xiàn)計(jì)劃從城市

到城市

鋪設(shè)一條天然氣管道，請(qǐng)?jiān)O(shè)計(jì)出最小價(jià)格管道鋪設(shè)方案.

本質(zhì)是求從城市到城市的一條最短路19第十九頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型解：寫出相應(yīng)的LINGO程序，MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortestroutefromcity1tocity7;3]

4]sets:5]!Hereisourprimitivesetofsevencities;6]cities/A,B1,B2,C1,C2,C3,D/;7]8]!TheDerivedset"roads"liststheroadsthat9]existbetweenthecities;20第二十頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

10]roads(cities,cities)/11]A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C312]C1,DC2,DC3,D/:w,x;13]endsets14]15]data:16]!Herearethedistancesthatcorrespond

17]toabovelinks;18]w=24331231134;19]enddata

21第二十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(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;END22第二十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型在上述程序中，21]句中的n=@size(cities)是計(jì)算集cities的個(gè)數(shù)，這里的計(jì)算結(jié)果是,這樣編寫方法目的在于提高程序的通用性.22]句表示目標(biāo)函數(shù),即求道路的最小權(quán)值.23],24]句表示約束中的情況，即最短路中中間點(diǎn)的約束條件.25]句表示約束中的情況，即最短路中起點(diǎn)的約束.約束中的情況，也就是最短路中終點(diǎn)的情況，沒有列在程序中，因?yàn)榻K點(diǎn)的約束方程與前個(gè)方程相關(guān).當(dāng)然，如果你將此方程列入到LINGO程序中，計(jì)算時(shí)也不會(huì)出現(xiàn)任何問(wèn)題，因?yàn)長(zhǎng)INGO軟件可以自動(dòng)刪除描述線性規(guī)劃可行解中的多余方程.23第二十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

LINGO軟件計(jì)算結(jié)果（僅保留非零變量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCostX(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路長(zhǎng)為6個(gè)單位.24第二十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

例（無(wú)向圖的最短路問(wèn)題）求下圖中到的最短路.本例是處理無(wú)向圖的最短路問(wèn)題，在處理方式上與有向圖的最短路有一些差別.25第二十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

解：對(duì)于無(wú)向圖的最短路問(wèn)題，可以這樣理解，從點(diǎn)到點(diǎn)和點(diǎn)到點(diǎn)的邊看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路問(wèn)題來(lái)編程序，但按照這種方法編寫LINGO程序相當(dāng)于邊（?。┰黾恿艘槐?這里選擇鄰接矩陣和賦權(quán)矩陣的方法編寫LINGO程序.MODEL:1]sets:2]cities/1..11/;3]roads(cities,cities):p,w,x;4]endsets26第二十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

5]data:6]p=011100000007]001010000008]010111100009]0010001000010]0110010110011]0010101010012]0011010011013]0000100010114]0000111101115]0000001010116]00000000000;27第二十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型

17]w=0281000000018]2060100000019]8607512000020]1070009000021]0150030290022]0010304060023]0029040031024]0000200070925]0000963701226]0000001010427]00000009240;28]enddata28第二十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期三最短路徑問(wèn)題的0-1規(guī)劃模型29]n=@size(cities);30]min=@sum(roads:w*x);31]@for(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)));

34]@su