數(shù)學(xué)建模校車安排問題 標(biāo)準(zhǔn)答案 答案僅供參考

1、摘 要根據(jù)對某市某一高校校車的老校區(qū)各區(qū)的距離和教師人數(shù)的調(diào)查資料，建立其數(shù)學(xué)模型，依據(jù)建立的停車站的位置及個(gè)數(shù)的不同而造成不同的滿意程度，制定建立停車站的位置及數(shù)目，根據(jù)具體情況提出自己的的建議與意見。 模型一：最短距離模型。通過對已知的兩個(gè)不同區(qū)的距離，根據(jù)Dijkstra算法算出各個(gè)區(qū)之間的最短距離。得到需要的分析數(shù)據(jù)。 模型二：多源最短距離。通過模型一中得到的數(shù)據(jù)，用多源最短路徑算法，求出建立不同個(gè)數(shù)的停車站時(shí)的最短路徑。再次考慮人的滿意程度，求出最大滿意度。 模型三：多目標(biāo)最優(yōu)規(guī)劃。通過以模型二的滿意程度和最小數(shù)量的車為雙目標(biāo)，建立設(shè)有3個(gè)乘車站時(shí)的最優(yōu)化解法。關(guān)鍵詞 停車站；Dij

2、kstra算法；滿意度；多目標(biāo)目標(biāo)；最優(yōu)解法校車安排問題 問題重述許多學(xué)校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車送到新校區(qū)。由于每天到新校區(qū)的教師和工作人員很多，往往需要安排許多車輛。如何有效的安排車輛及讓教師和工作人員盡量滿意是個(gè)十分重要的問題。現(xiàn)有如下問題請你設(shè)計(jì)解決。假設(shè)老校區(qū)的教師和工作人員分布在50個(gè)區(qū)，各區(qū)的距離見表1(第3-4頁)。各區(qū)人員分布見表2(第6頁)。問題1：如要建立個(gè)乘車點(diǎn)，為使各區(qū)人員到最近乘車點(diǎn)的距離最小，該將校車乘車點(diǎn)應(yīng)建立在哪個(gè)點(diǎn)。建立一般模型，并給出時(shí)的結(jié)果。 問題2：若考慮每個(gè)區(qū)的乘車人數(shù)，為使教師和工作人員滿意度最大，該將校車乘車點(diǎn)應(yīng)建立在

3、哪個(gè)點(diǎn)。建立一般模型，并給出時(shí)的結(jié)果。 問題3 若建立3個(gè)乘車點(diǎn)，為使教師和工作人員盡量滿意，至少需要安排多少輛車？給出每個(gè)乘車點(diǎn)的位置和車輛數(shù)。設(shè)每輛車最多載客47人。問題4；關(guān)于校車安排問題，你還有什么好的建議和考慮。可以提高乘車人員的滿意度，又可節(jié)省運(yùn)行成本。2、模型假設(shè) （1）假設(shè)每個(gè)人的的滿意程度只與距離有關(guān)。 （2）假設(shè)原數(shù)據(jù)沒告訴的兩個(gè)區(qū)之間沒有道路，即只有經(jīng)過其它的區(qū)往返。 （3）假設(shè)總的滿意度是所有人的滿意度之和。（4）假設(shè)每個(gè)人都很聰明，即只會(huì)選擇最近的路徑去停車站。（5）假設(shè)每次出發(fā)所有人一起走，即沒有次序的先后（校車高峰期）。（6）假設(shè)車的數(shù)量的決策權(quán)比人的滿意度的決策

4、權(quán)高，可為正比于它的平方，立方甚至更高。（7）假設(shè)車只在起始點(diǎn)載人，即使人沒載滿，在中途也不停車。模型建立及求解模型三多目標(biāo)最有規(guī)劃模型二多源最短路徑模型一最短路徑模型模型四模型檢驗(yàn) 最短路徑問題 我們?yōu)榱饲蟪龈鱾€(gè)區(qū)的之間的最短的路徑，用Dijstra算法求解。 Dijkstra算法是圖論中非常有名的一個(gè)算法。圖采用鄰接矩陣的形式描述，mij表示結(jié)點(diǎn)i到結(jié)點(diǎn)j間的代價(jià)，如果沒有直接因果關(guān)系，則為無窮大，計(jì)算機(jī)中可以用一個(gè)很大的數(shù)據(jù)代替（如Matlab中的inf）。但Dijkstra算法只能求出從結(jié)點(diǎn)i到其它各結(jié)點(diǎn)的最短路徑。算法引入這樣兩個(gè)集合s和t，s是那些已經(jīng)確定了到i結(jié)點(diǎn)的最短路徑的結(jié)點(diǎn)

5、，t為全集u和s的差集，即那些還未確定最短路徑的結(jié)點(diǎn)。而且s的初值是i，t的初值是u-i。另外再引入一個(gè)標(biāo)記數(shù)組dn，其中在某一步dk表示當(dāng)前從i到k的較短路徑，dk的初值為mik。整個(gè)算法過程如下：、 在t中選擇一個(gè)dk最小的結(jié)點(diǎn)k，將k并入s，并從t中去掉，如果t為則轉(zhuǎn)到；、 用k結(jié)點(diǎn)和t中其余結(jié)點(diǎn)進(jìn)行一遍比較，如果didk+mki，則用dk+mki取代原來的di，重復(fù)；、 算法結(jié)束，此時(shí)dk中保存的就是從到k結(jié)點(diǎn)的最短路徑。算法就以這樣非常簡單的形式完成了求解，時(shí)間復(fù)雜度是O(n2)，確定了從到其余各結(jié)點(diǎn)的最短路徑。由下表可以建立原始矩陣w。表1 各區(qū)距離表區(qū)域號區(qū)域號距離(m)1240

6、013450243002212302471403460045210419310562305720067320683407817071816089200815285910180101115010151601112140111413012132001334400141519014261901516170151725016171401618130172724018192041825180192014019241752021180202419021223002123270214735022441602245270224818023242402329210233029023441502425170242

7、813026271402634320272819028292602931190303124030421303043210313223031362603150210323319032351403236240333421035371603639180364019037381353839130394131040411404050190425020043442604345210454624046482804849200 本題由于有50個(gè)點(diǎn)，數(shù)據(jù)較多，故使用了matlab求解。使用for循環(huán)可以分別算出從1開始到49到各個(gè)點(diǎn)的最短距離。（程序如附錄1） 所求的答案見附錄2中的b。使用matlab作圖工具

8、畫出了其中各區(qū)間的距離。如下圖：多源最短距離和 3.2.1 問題一50個(gè)點(diǎn)中選擇n個(gè)做為停車站，其余剩下的（50-n）個(gè)區(qū)的老師根據(jù)假（4），則要選擇最近的路徑到所要乘車的站。不滿意度為最短的距離。假設(shè)50個(gè)區(qū)為固定的50個(gè)定點(diǎn)，可以用到模型一中的a數(shù)據(jù)。先從50個(gè)點(diǎn)中取出n個(gè)，在分別比較這n個(gè)數(shù)所在的行向量在同一列時(shí)的最小值相加，即不滿意度M=j=1nminai,j j=1、2、3 （M值越小，越滿意）得到50n個(gè)距離之和，比較這些數(shù)找出最小值，同時(shí)記錄該n個(gè)數(shù)所在的行數(shù)，即為所建的停車站的位置。 3.2.2 問題二 考慮人數(shù)的影響，人數(shù)見下表： 表2 各區(qū)人員分布區(qū)域人數(shù)區(qū)域人數(shù)16526

9、162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484467205445202149461822124768235448722446497625765062由人數(shù)建立矩陣b(見附錄)，由假設(shè)(1)可知，老師及工作人員的不滿意度為教師人數(shù)與所距離最近的車站的之商的和。該問題的決策矩陣是 c(i,j)=a(i,j)./b(j)同3.2.1建立的模型帶入c即可求出最小路徑所需建立的乘車站

10、。M1=j=1nminci,j j=1、2、3由附錄2可知： 對于問題1：當(dāng)n=2時(shí)，可以求出其所建的地址是（18，31） 最小不滿意度M=24492當(dāng)n=3時(shí)，由附錄可以求出其所建的地址是（15，21，31），最小不滿意度M=19660對于問題2：當(dāng)n=2時(shí)附錄，建立車站的區(qū)是（16，32）最小不滿意度M1=661當(dāng)n=3時(shí)附錄，建立車站的區(qū)是（16，32，48），最小不滿意度為M1=32 由假設(shè)(5)(7)可以知道最少需要的車的數(shù)量。設(shè)人的總數(shù)是N=2502，則最少需要的車的數(shù)量是n=N/47+1=54輛。若建立三個(gè)站，則做多需要的車為56輛。根據(jù)問題3.2.1，當(dāng)n=3時(shí)，可以用同法求出

11、建立在不同的位置的三維矩陣，其值為建在這三點(diǎn)所需要的車的數(shù)量（其余各點(diǎn)為inf，代表不能在該點(diǎn)選址，即不能選同一個(gè)點(diǎn)做兩次車站）。得到三維方陣t，而3.2.1可得教師及工作人員的不滿意度的三維方陣t1（各點(diǎn)為算選的三個(gè)點(diǎn)的分別不滿意度）.可成立最新的方陣v，又由假設(shè)(6),不滿意度M2為人員不滿意度與車輛不滿意度的平方之可以得到最優(yōu)規(guī)劃的矩陣是 v=t1.*(t.i) i=2 ，3，4，5求出最小值所在的空間坐標(biāo)即為要選擇的建乘車站的區(qū)。設(shè)到最小不滿意度的三站的人數(shù)分別人p(i)，則每站需要的車為n=p(i)/47+1(程序見附錄3)i=2，可得建立的位置是（16，32，43），最小不滿意度為

12、M2= 105分別安排11，17，26輛車。i=3，可得建立的位置是（16，32，43），最小不滿意度為M2= 107分別安排11，17，26輛車。109分別安排11，17，26輛車。i=5，可得建立的位置是（16，32，43），最小不滿意度為M2= 1011分別安排11，17，26輛車。綜合上述的答案，可以明確的知道應(yīng)該建立車站的位置是（16，32，43），分別安排11，17，26輛車。 模型分析和驗(yàn)證 = 1 * GB3 誤差分析由于使用了遞歸和準(zhǔn)確的數(shù)據(jù)，沒有計(jì)算誤差。就實(shí)際而言，考慮的問題方面較少，與實(shí)際仍有些許誤差。 = 2 * GB3 靈敏度分析 對于模型三，當(dāng)使用的權(quán)重不同時(shí)，產(chǎn)

13、生的結(jié)果完全一致，故權(quán)重的靈敏度不是很高。主要取決于車的數(shù)量的影響和人的滿意度的影響，同時(shí)車的數(shù)量的影響較大。 = 3 * GB3 模型分析 對于所建立的三個(gè)模型，充分考慮了所給我全部數(shù)據(jù)，并做了合理的假設(shè)，所以三個(gè)模型都具有很強(qiáng)的準(zhǔn)確性和可行性。 模型一使用Dijkstra算法先求出了從區(qū)1到其余49個(gè)的最短路徑，在使用循環(huán)求出各個(gè)區(qū)的最短路徑。 模型二雖然計(jì)算有些繁重，但為了準(zhǔn)確的數(shù)據(jù)，亦可以放棄某些簡便算法。 模型三對影響的充分考慮，得出不同的權(quán)重的情況，有很高的準(zhǔn)確性。 總之，本模型的建立的在追求準(zhǔn)確的基礎(chǔ)上，建立優(yōu)化的模型，得出最符合實(shí)際的解。 = 4 * GB3 對問題4的回答由增

14、加站臺數(shù)，人的滿意度就會(huì)越來越高，所以可以適當(dāng)?shù)脑O(shè)置站臺數(shù)從而使人的滿意度和學(xué)校建立站臺的數(shù)目達(dá)到最佳的切合。由模型二可以求出分別站臺是1，27的不滿意度，分別為404.787234，315.107761，261.0157320，224.299246，203.996505，184.723942.用matlab作圖可得如下的擬合曲線。 有圖就可以確立建立的數(shù)目與人不滿意度的關(guān)系y=-1.6266*x3+*x2*x+誤差分析： （2）由模型三可以知道最少的車輛是（53+所設(shè)立的站臺數(shù)），可以把相近的幾個(gè)站臺的拉不滿的人數(shù)整合后放入一輛車中，從而減少車的數(shù)目。同時(shí)可以采購多種型號大小的校車，做到能正

15、好使各停車站的老師能正好乘坐，即不遺漏一個(gè)老師，不空一個(gè)座位。 為了檢驗(yàn)數(shù)據(jù)的準(zhǔn)確性，用matlab分別對n=2、3進(jìn)行驗(yàn)證（見附錄4），所得結(jié)果和原始結(jié)果完全吻合，故說明建立模型的準(zhǔn)確性。5、模型評價(jià)、改進(jìn)和推廣5.1 模型的優(yōu)點(diǎn) 模型建立的合理性，模型的建立是在對所給的數(shù)據(jù)進(jìn)行充分的挖掘的基礎(chǔ)之上的，通過數(shù)據(jù)之間的關(guān)系提煉出各個(gè)區(qū)之間的關(guān)系，建立起模型； 對一些未量化的指標(biāo)建立模型，進(jìn)行合理的量化，例如對人的模型二中不滿意度的考慮，以及模型三中的建立不滿意度所加的指標(biāo)。運(yùn)用了精確地算法，準(zhǔn)確的求出了多源最短路徑的問題； 模型的建立是按照問題的解決的思路進(jìn)行的，首先分析和發(fā)現(xiàn)現(xiàn)有規(guī)律，然后對

16、現(xiàn)有的規(guī)律進(jìn)行評價(jià)，最后進(jìn)行建模； 模型的缺點(diǎn) 為了簡化模型的求解，本文中將所有的人的滿意度隨距離的成正比，可能對模型的求解帶來一定的誤差； 本文中并沒有過多的考慮了模型中的數(shù)據(jù)中不是很重要的因素，如車的不同時(shí)間出發(fā)可能引起的變化； = 3 * GB3 模型運(yùn)算時(shí)間較長，如果需要求得建立7個(gè)以上的停車站的最優(yōu)解，利用普通計(jì)算機(jī)求解耗時(shí)很多5.3 模型的改進(jìn) = 1 * GB3 針對缺點(diǎn)一：參考一些比較權(quán)威的資料和調(diào)查求出對不同人的滿意度與距離的關(guān)系進(jìn)行估計(jì)，然后進(jìn)行求解； 針對缺點(diǎn)二：可以充分的考慮不同時(shí)間的不同的人數(shù)到停車站的差異，求出最少使用的車。 = 3 * GB3 針對缺點(diǎn)三：可以用圖

17、論的方法求解。或用計(jì)算機(jī)畫出每個(gè)點(diǎn)之間的最短距離，再求解。可以解多源的最短路徑問題，特別是二源、三源問題具有很高的準(zhǔn)確性。6、參考文獻(xiàn)1.A First Course in Mathenmatical Moderling (Third Edition)2. 數(shù)學(xué)建?；A(chǔ) 薛疑3.數(shù)學(xué)建模案例選集 姜啟源 謝金星4.數(shù)學(xué)建模及其基礎(chǔ)知識詳解 王文波 5.大學(xué)生數(shù)學(xué)建模競賽輔導(dǎo)教材 葉其效6.初等數(shù)學(xué)建模 黃忠裕7.基于matlab 動(dòng)態(tài)規(guī)劃中最短路線的實(shí)現(xiàn)程序 J電腦學(xué)習(xí) 施益昌 鄭賢斌 李自立8.校車調(diào)度的數(shù)學(xué)模型 吳亞敏 鄂東職業(yè)技術(shù)學(xué)院 消費(fèi)導(dǎo)刊9. 最優(yōu)花理論教案10.數(shù)學(xué)模型 李立剛附

18、錄1用matlab求任意兩個(gè)校區(qū)的最短距離%Dijstra算法求解clear allclcw=0,400,450,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;400,0,inf,300,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

19、nf,inf,inf,inf,inf,inf,230,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,140,inf,inf,inf;450,inf,0,600,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

20、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,300,600,0,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,310,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,210,0,230,200,inf,inf,inf,inf,inf,inf,inf,inf,inf

21、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,230,0,320,340,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

22、nf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,200,320,0,170,inf,inf,inf,inf,inf,inf,inf,inf,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,340,170,0,200,inf,inf,inf,inf,inf,285,inf,inf,i

23、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,200,0,180,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

24、,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,180,0,150,inf,inf,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,150,0,140,inf,130,inf,inf,inf,inf,inf

25、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,140,0,200,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

26、nf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,200,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,400,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,130,inf,inf,0,190,inf,inf,inf,inf,inf,i

27、nf,inf,inf,inf,inf,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,285,inf,160,inf,inf,inf,190,0,170,250,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

28、,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,170,0,140,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,250,140,0,inf,inf,inf,inf,inf

29、,inf,inf,inf,inf,240,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,130,inf,0,204,inf,inf,inf,inf,inf,180,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

30、nf,inf,inf;inf,inf,inf,310,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,204,0,140,inf,inf,inf,175,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,140,0,180,inf,inf,1

31、90,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,230,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,0,300,270,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,350,inf,inf

32、,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,300,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,160,270,inf,inf,180,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,270,inf,0,240,inf

33、,inf,inf,inf,210,290,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,150,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,175,190,inf,inf,240,0,170,inf,inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;i

34、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,inf,inf,inf,inf,inf,170,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,1

35、40,inf,inf,inf,inf,inf,inf,320,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,240,inf,inf,inf,inf,inf,inf,inf,inf,140,0,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf

36、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,130,inf,inf,190,0,260,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210,inf,inf,inf,inf,2

37、60,0,inf,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,290,inf,inf,inf,inf,inf,inf,0,240,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,130,210,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,i

38、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,240,0,230,inf,inf,inf,260,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

39、,inf,230,0,190,inf,140,240,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,0,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf

40、,inf,inf,inf,inf,inf,inf,inf,400,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,320,inf,inf,inf,inf,inf,inf,210,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

41、nf,140,inf,inf,0,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,260,240,inf,inf,inf,0,inf,inf,180,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,i

42、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,160,inf,0,135,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

43、,inf,inf,inf,inf,135,0,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,inf,130,0,inf,310,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf

44、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,inf,inf,inf,0,140,inf,inf,inf,inf,inf,inf,inf,inf,190;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

45、nf,inf,inf,inf,inf,310,140,0,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,200;inf,inf,inf,inf,inf,inf,inf,inf,inf,i

46、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,260,210,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,160,150,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

47、,inf,inf,inf,inf,inf,inf,inf,260,0,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,270,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210,inf,0,240,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

48、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,240,0,inf,280,inf,inf;inf,140,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,350,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

49、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,280,inf,0,200,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

50、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,200,0,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210,inf,inf,inf,inf,inf,inf,inf

51、,inf,190,inf,200,inf,inf,inf,inf,inf,inf,inf,0;for p=1:50 n=size(w,1); w1=w(p,:); for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1; while kl(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u; end end end end ll=l; for i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf; end end end lv=inf; for i=1:n if

52、ll(i)lv lv=ll(i); v=i; end end s(k+1)=v; k=k+1; u=s(k); endif p=1 a=l;else a=a;l;endenddisp(a);2.用c+求n個(gè)點(diǎn)的多源最小路徑#include using namespace std;/各點(diǎn)距離方陣 d為附錄一中的aint d5050=0,400,450,700,910,1140,1110,1280,1480,1614,1764,1904,2104,1644,1454,1284,1424,1154,950,810,630,930,900,1000,1170,1460,1320,1130,1110,1

53、190,1300,1530,1720,1780,1670,1560,1830,1870,1740,1700,1840,1320,1310,1050,1200,1390,540,1110,1310,1510,400,0,850,300,510,740,710,880,1080,1214,1364,1504,1704,1244,1054,884,1024,754,550,410,230,530,500,600,770,1060,920,730,710,790,900,1130,1320,1380,1270,1160,1430,1470,1340,1300,1440,920,910,650,800,

54、990,140,710,910,1110,450,850,0,600,810,1040,1010,1180,1380,1560,1710,1850,2050,1604,1414,1244,1384,1114,910,1050,1080,1380,1325,1085,1255,1545,1405,1215,1475,1615,1665,1895,2075,1865,2035,1925,2195,2235,2105,2065,2205,1745,1735,1475,1650,1840,990,1560,1760,1875,700,300,600,0,210,440,410,580,780,960,

55、1110,1250,1450,1004,814,644,784,514,310,450,530,830,725,485,655,945,805,615,875,1015,1065,1295,1475,1265,1435,1325,1595,1635,1505,1465,1605,1145,1135,875,1100,1290,440,1010,1210,1275,910,510,810,210,0,230,200,370,570,750,900,1040,1240,845,655,490,630,360,520,660,740,1040,935,695,540,1010,870,825,108

56、5,1225,1275,1505,1540,1330,1645,1535,1805,1845,1715,1675,1815,1355,1345,1085,1310,1500,650,1220,1420,1485,1140,740,1040,440,230,0,320,340,540,720,870,1010,1210,815,625,610,750,480,684,824,970,1270,1070,830,660,1005,990,960,1220,1360,1410,1640,1535,1325,1780,1670,1940,1980,1850,1810,1950,1490,1480,12

57、20,1540,1730,880,1450,1650,1620,1110,710,1010,410,200,320,0,170,370,550,700,840,1040,645,455,290,430,160,364,504,684,984,750,510,340,810,670,640,900,1040,1090,1320,1340,1130,1460,1350,1620,1660,1530,1490,1630,1170,1160,900,1254,1444,850,1164,1364,1300,1280,880,1180,580,370,340,170,0,200,380,530,670,

58、870,475,285,455,535,330,534,674,854,1154,920,680,510,665,775,810,1070,1210,1260,1385,1195,985,1525,1520,1685,1820,1700,1660,1800,1340,1330,1070,1424,1614,1020,1334,1534,1470,1480,1080,1380,780,570,540,370,200,0,180,330,470,670,460,340,510,590,530,734,874,1054,1354,1120,880,710,650,790,980,1240,1410,

59、1430,1370,1180,970,1510,1610,1670,1805,1790,1800,1940,1540,1530,1270,1624,1814,1220,1534,1734,1640,1614,1214,1560,960,750,720,550,380,180,0,150,290,490,280,160,330,410,460,664,804,984,1284,1050,810,640,470,610,800,1060,1340,1250,1190,1000,790,1330,1430,1490,1625,1610,1620,1760,1470,1460,1200,1554,17

60、44,1334,1464,1664,1460,1764,1364,1710,1110,900,870,700,530,330,150,0,140,340,130,310,480,560,610,814,954,1134,1330,1020,780,790,320,460,650,910,1310,1100,1040,850,640,1180,1280,1340,1475,1460,1470,1610,1440,1430,1170,1600,1790,1484,1510,1710,1310,1904,1504,1850,1250,1040,1010,840,670,470,290,140,0,2