数学建模校车安排问题 标准答案 答案仅供参考

1、摘 要根据对某市某一高校校车的老校区各区的距离和教师人数的调查资料，建立其数学模型，依据建立的停车站的位置及个数的不同而造成不同的满意程度，制定建立停车站的位置及数目，根据具体情况提出自己的的建议与意见。 模型一：最短距离模型。通过对已知的两个不同区的距离，根据Dijkstra算法算出各个区之间的最短距离。得到需要的分析数据。 模型二：多源最短距离。通过模型一中得到的数据，用多源最短路径算法，求出建立不同个数的停车站时的最短路径。再次考虑人的满意程度，求出最大满意度。 模型三：多目标最优规划。通过以模型二的满意程度和最小数量的车为双目标，建立设有3个乘车站时的最优化解法。关键词 停车站；Dij

2、kstra算法；满意度；多目标目标；最优解法校车安排问题 问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在50个区，各区的距离见表1(第3-4页)。各区人员分布见表2(第6页)。问题1：如要建立个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在

3、哪个点。建立一般模型，并给出时的结果。 问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。问题4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2、模型假设 （1）假设每个人的的满意程度只与距离有关。 （2）假设原数据没告诉的两个区之间没有道路，即只有经过其它的区往返。 （3）假设总的满意度是所有人的满意度之和。（4）假设每个人都很聪明，即只会选择最近的路径去停车站。（5）假设每次出发所有人一起走，即没有次序的先后（校车高峰期）。（6）假设车的数量的决策权比人的满意度的决策

4、权高，可为正比于它的平方，立方甚至更高。（7）假设车只在起始点载人，即使人没载满，在中途也不停车。模型建立及求解模型三多目标最有规划模型二多源最短路径模型一最短路径模型模型四模型检验 最短路径问题 我们为了求出各个区的之间的最短的路径，用Dijstra算法求解。 Dijkstra算法是图论中非常有名的一个算法。图采用邻接矩阵的形式描述，mij表示结点i到结点j间的代价，如果没有直接因果关系，则为无穷大，计算机中可以用一个很大的数据代替（如Matlab中的inf）。但Dijkstra算法只能求出从结点i到其它各结点的最短路径。算法引入这样两个集合s和t，s是那些已经确定了到i结点的最短路径的结点

5、，t为全集u和s的差集，即那些还未确定最短路径的结点。而且s的初值是i，t的初值是u-i。另外再引入一个标记数组dn，其中在某一步dk表示当前从i到k的较短路径，dk的初值为mik。整个算法过程如下：、 在t中选择一个dk最小的结点k，将k并入s，并从t中去掉，如果t为则转到；、 用k结点和t中其余结点进行一遍比较，如果didk+mki，则用dk+mki取代原来的di，重复；、 算法结束，此时dk中保存的就是从到k结点的最短路径。算法就以这样非常简单的形式完成了求解，时间复杂度是O(n2)，确定了从到其余各结点的最短路径。由下表可以建立原始矩阵w。表1 各区距离表区域号区域号距离(m)1240

6、013450243002212302471403460045210419310562305720067320683407817071816089200815285910180101115010151601112140111413012132001334400141519014261901516170151725016171401618130172724018192041825180192014019241752021180202419021223002123270214735022441602245270224818023242402329210233029023441502425170242

7、813026271402634320272819028292602931190303124030421303043210313223031362603150210323319032351403236240333421035371603639180364019037381353839130394131040411404050190425020043442604345210454624046482804849200 本题由于有50个点，数据较多，故使用了matlab求解。使用for循环可以分别算出从1开始到49到各个点的最短距离。（程序如附录1） 所求的答案见附录2中的b。使用matlab作图工具

8、画出了其中各区间的距离。如下图：多源最短距离和 3.2.1 问题一50个点中选择n个做为停车站，其余剩下的（50-n）个区的老师根据假（4），则要选择最近的路径到所要乘车的站。不满意度为最短的距离。假设50个区为固定的50个定点，可以用到模型一中的a数据。先从50个点中取出n个，在分别比较这n个数所在的行向量在同一列时的最小值相加，即不满意度M=j=1nminai,j j=1、2、3 （M值越小，越满意）得到50n个距离之和，比较这些数找出最小值，同时记录该n个数所在的行数，即为所建的停车站的位置。 3.2.2 问题二 考虑人数的影响，人数见下表： 表2 各区人员分布区域人数区域人数16526

9、162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484467205445202149461822124768235448722446497625765062由人数建立矩阵b(见附录)，由假设(1)可知，老师及工作人员的不满意度为教师人数与所距离最近的车站的之商的和。该问题的决策矩阵是 c(i,j)=a(i,j)./b(j)同3.2.1建立的模型带入c即可求出最小路径所需建立的乘车站

10、。M1=j=1nminci,j j=1、2、3由附录2可知： 对于问题1：当n=2时，可以求出其所建的地址是（18，31） 最小不满意度M=24492当n=3时，由附录可以求出其所建的地址是（15，21，31），最小不满意度M=19660对于问题2：当n=2时附录，建立车站的区是（16，32）最小不满意度M1=661当n=3时附录，建立车站的区是（16，32，48），最小不满意度为M1=32 由假设(5)(7)可以知道最少需要的车的数量。设人的总数是N=2502，则最少需要的车的数量是n=N/47+1=54辆。若建立三个站，则做多需要的车为56辆。根据问题3.2.1，当n=3时，可以用同法求出

11、建立在不同的位置的三维矩阵，其值为建在这三点所需要的车的数量（其余各点为inf，代表不能在该点选址，即不能选同一个点做两次车站）。得到三维方阵t，而3.2.1可得教师及工作人员的不满意度的三维方阵t1（各点为算选的三个点的分别不满意度）.可成立最新的方阵v，又由假设(6),不满意度M2为人员不满意度与车辆不满意度的平方之可以得到最优规划的矩阵是 v=t1.*(t.i) i=2 ，3，4，5求出最小值所在的空间坐标即为要选择的建乘车站的区。设到最小不满意度的三站的人数分别人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辆车。综合上述的答案，可以明确的知道应该建立车站的位置是（16，32，43），分别安排11，17，26辆车。 模型分析和验证 = 1 * GB3 误差分析由于使用了递归和准确的数据，没有计算误差。就实际而言，考虑的问题方面较少，与实际仍有些许误差。 = 2 * GB3 灵敏度分析 对于模型三，当使用的权重不同时，产

13、生的结果完全一致，故权重的灵敏度不是很高。主要取决于车的数量的影响和人的满意度的影响，同时车的数量的影响较大。 = 3 * GB3 模型分析 对于所建立的三个模型，充分考虑了所给我全部数据，并做了合理的假设，所以三个模型都具有很强的准确性和可行性。 模型一使用Dijkstra算法先求出了从区1到其余49个的最短路径，在使用循环求出各个区的最短路径。 模型二虽然计算有些繁重，但为了准确的数据，亦可以放弃某些简便算法。 模型三对影响的充分考虑，得出不同的权重的情况，有很高的准确性。 总之，本模型的建立的在追求准确的基础上，建立优化的模型，得出最符合实际的解。 = 4 * GB3 对问题4的回答由增

14、加站台数，人的满意度就会越来越高，所以可以适当的设置站台数从而使人的满意度和学校建立站台的数目达到最佳的切合。由模型二可以求出分别站台是1，27的不满意度，分别为404.787234，315.107761，261.0157320，224.299246，203.996505，184.723942.用matlab作图可得如下的拟合曲线。 有图就可以确立建立的数目与人不满意度的关系y=-1.6266*x3+*x2*x+误差分析： （2）由模型三可以知道最少的车辆是（53+所设立的站台数），可以把相近的几个站台的拉不满的人数整合后放入一辆车中，从而减少车的数目。同时可以采购多种型号大小的校车，做到能正

15、好使各停车站的老师能正好乘坐，即不遗漏一个老师，不空一个座位。 为了检验数据的准确性，用matlab分别对n=2、3进行验证（见附录4），所得结果和原始结果完全吻合，故说明建立模型的准确性。5、模型评价、改进和推广5.1 模型的优点 模型建立的合理性，模型的建立是在对所给的数据进行充分的挖掘的基础之上的，通过数据之间的关系提炼出各个区之间的关系，建立起模型； 对一些未量化的指标建立模型，进行合理的量化，例如对人的模型二中不满意度的考虑，以及模型三中的建立不满意度所加的指标。运用了精确地算法，准确的求出了多源最短路径的问题； 模型的建立是按照问题的解决的思路进行的，首先分析和发现现有规律，然后对

16、现有的规律进行评价，最后进行建模； 模型的缺点 为了简化模型的求解，本文中将所有的人的满意度随距离的成正比，可能对模型的求解带来一定的误差； 本文中并没有过多的考虑了模型中的数据中不是很重要的因素，如车的不同时间出发可能引起的变化； = 3 * GB3 模型运算时间较长，如果需要求得建立7个以上的停车站的最优解，利用普通计算机求解耗时很多5.3 模型的改进 = 1 * GB3 针对缺点一：参考一些比较权威的资料和调查求出对不同人的满意度与距离的关系进行估计，然后进行求解； 针对缺点二：可以充分的考虑不同时间的不同的人数到停车站的差异，求出最少使用的车。 = 3 * GB3 针对缺点三：可以用图

17、论的方法求解。或用计算机画出每个点之间的最短距离，再求解。可以解多源的最短路径问题，特别是二源、三源问题具有很高的准确性。6、参考文献1.A First Course in Mathenmatical Moderling (Third Edition)2. 数学建模基础 薛疑3.数学建模案例选集 姜启源 谢金星4.数学建模及其基础知识详解 王文波 5.大学生数学建模竞赛辅导教材 叶其效6.初等数学建模 黄忠裕7.基于matlab 动态规划中最短路线的实现程序 J电脑学习 施益昌 郑贤斌 李自立8.校车调度的数学模型 吴亚敏 鄂东职业技术学院 消费导刊9. 最优花理论教案10.数学模型 李立刚附

18、录1用matlab求任意两个校区的最短距离%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个点的多源最小路径#include using namespace std;/各点距离方阵 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