最短路徑問題

最短路徑問題摘要在圖論當中，任意兩點間的最短路徑問題，運用Dijkstra算法，F(xiàn)lord算法,匈牙利算法等都可以就解決這類相關問題,本文主要就是運用圖論相關知識，來分析問題的。在問題一中，需要為貨車司機選擇一條從地點1到地點11的最短時間問題，其實際歸結為求一個兩點間最短路徑問題，運用運籌學中的網(wǎng)絡模型相關知識，建立了一個一個0-1線性模型，并最終求的其結果，最短時間為21，貨車司機的運輸路線為VtVtVtVtV。1891011運用Floyd算法解決問題二，并且運用Matlab軟件編程,Floyd算法與Matlab軟件編程所得出的結果一致，最后得出了一個最短航程表，及任意兩點間的最短航程圖。本文的最大亮點在于將問題二進行更深一步的拓展，從問題實際出發(fā)，從公司的差旅費用最小出發(fā)，利用Mtlab軟件編程的出了公司到個城市間差旅費用最小圖，從而更能為公司節(jié)省成本。C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市間差旅費用最小其次是本文結果的準確性，問題一運用Lingo軟件編程，和WinQSB軟件，所得出結果都是一致的，問題二更是運用Floyd算法，Matlab軟件編程，WinQSB軟件，大大地保證了結果的準確性，并且十分恰當?shù)剡\用WinQSB軟件將作圖功能，把每一提的最短路徑都清晰的描繪出來，更加直觀地將結果展現(xiàn)出來。關鍵字：MatlabLingoWinQSBFloyd算法0-1規(guī)劃#附錄五問題二在進行Floydj算法進行插值時，每次插值所發(fā)生的選擇路徑的變化：P3=r112111、r11@111、P3=r112111、r11@111、2222[32222202233332@33330PA=「44444444444445[355515[4555gV662616丿v6606@6丿11p51國國1224333444455564641]2444V605511'2242333444444555464646丿r111111「「11111]222212222212343434343434P2二回434343434回4515551515551V666616丿「V66回616丿附錄六問題二用Matlab軟件編程程序與運行結果：>>clear>>n=6;>>a=zeros(n);>>a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;>>a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;>>a(4,5)=10;a(4,6)=25;a(5,6)=55;>>a=a+a';M=max(max(a))*M2;%M為充分大的正實數(shù)>>a=a+((a==0)-eye(n))*M;>>path=zeros(n);>>fork=1:nfori=1:n

forj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendend>>a,path運行結果：a,patha=035453525103501520302545150102035352010010252530201003510253525350path=065600065600500500040004500040004000001010附錄七問題二的拓展用Matlab軟件編程程序與運行結果：>>n=6;>>a=zeros(n);>>a(1,2)=69.5;a(1,4)=61;a(1,5)=34;a(1,6)=16;>>a(2,1)=71;a(2,3)=24;a(2,4)=32;a(2,6)=40;>>a(3,2)=24;a(3,4)=16;a(3,5)=32;>>a(4,1)=53.5;a(4,2)=32;a(4,3)=16;a(4,5)=16;a(4,6)=38.5;>>a(5,1)=34;a(5,3)=27.5;a(5,4)=16;a(5,6)=76;>>a(6,1)=14.8;a(6,2)=35.5;a(6,4)=34.3;a(6,5)=76;>>M=max(max(a))*n^2;>>a=a+((a==0)-eye(n))*M;>>path=zeros(n);>>fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendend>>a,path問題二拓展Matlab運行結果a=051.500061.500050.000034.000016.000054.8000024.000032.000048.000040.000066.000024.0000016.000032.000054.500050.000032.000016.0000016.000038.500034.