最短路徑問(wèn)題

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