钟嘉鸣虞程凯郑明晔A环游世界路程规划问题的分析样本

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。环游世界路程规划问题的分析数学建模协会编号:28钟嘉鸣虞程凯郑明晔指导教师:房永飞评阅编号:评阅专家1评阅专家2评阅专家3评阅专家4评阅专家5摘要本文综合运用了Dijkstra算法、Floyd算法和最短路径问题的0—1规划模型等多种算法和Matlab、Lingo等多种编程软件,在确定以伦敦为起(终)点的环游世界的最佳(最短)路径、以其它地点为起(终)点的环游世界的最佳(最短)路径等两个问题上做出了严密的解答。解答过程层层递进,结果相互印证。首先对题目中所给的地图进行了预处理。将地图中左右两侧相同的地点进行了拼接,使之只出现一次,并将起点左侧与之相连的直线进行了切割,并填入序号为55的终点。而且根据单向(即向东)的路径网络(详见附录)将网络交通图抽象成为有(无)向图模型,得到带权邻接矩阵以便求解。然后经过Dijkstra算法、Floyd算法和最短路径问题的0—1规划三种算法对以伦敦为始、终点的环游世界的最佳(最短)路径问题进行了求解,用三种方法所得的最短路径和相应的天数完全相同,增加了所得结论的可靠性。对于第二问,经过Matlab的程序优化,本文建立通用的有向图模型,得到了通用的带权邻接矩阵,经过改进算法和程序,求得了以54个城市为起点环游世界的最短路径和相应的天数。从而得到能够在80天内环游世界并作为起点的城市,很好地解决了第二问。之后我们对模型进行了评价与检验,讨论了题中两段不确定路径对结果的影响,并对模型进行了推广应用。本文主要有三个亮点:第一、在第一个问中同时利用三种方法进行平行求解,并得到了完全相同的结论,说明了模型的可靠性;第二、基于第一问中的Floyd算法,建立通用的有向图模型和带权邻接矩阵,方便而快速地求得了以任何一点为起点环游世界的最短路径及相应天数;第三、在第二个问的基础上,我们又对模型进行了推广,并对模型提出了严谨的评价与检验,深入地分析了问题。关键字:最短路径Dijkstra算法Floyd算法0—1整数规划有向图模型正文部分问题重述本题以儒勒·凡尔纳的著名小说《环游世界80天》中,英国绅士福格在伦敦与人打赌环游世界的故事为背景,提出了路程规划的相关问题。在小说《环游世界80天》中,英国绅士福格在伦敦与人打赌能够在80天内环游世界,这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船,然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图,福格选择的是往东走,每段路线所需要的天数显示在图上,旅行的时间基于1872年能采用的旅行方式以及距离。要求解答以下两个问题:请设计一个算法为福格选择一条最佳路径,即环游世界天数最短,你选择的路径能让她赢得赌注吗?如果她在别的地方与人打赌,比如纽约或者上海,结果会怎样?图表SEQ图表\*ARABIC图表SEQ图表\*ARABIC1题图:从伦敦环游世界不同路线的交通网络图问题分析本题为典型的离散规划问题。对于问题一,是寻找路径最短的规划问题,能够由离散数学中Dijkstra算法、Floyd算法和0-1整数规划算法求解,得到的结果应该是一条具体的路径和相应的路程。对于问题二,根据解决第一问的方法,利用matlab编程找到以任何一个点为起点环绕地球一周所用的最短天数,从而找出在80天内能够环绕地球一周起点(与终点),即说明在这些点所代表的地方与别人打赌能够赢。本题涉及的点较多,而且数据以图片形式给出,需要对数据进行预处理。数据的预处理观察题图能够发现,图中有两段路径没有给出相应的路程,我们经过查找地图上两点之间的距离,类比于相似旅行方式的路径,按比例求出相应的路程。我们将利用Dijkstra算法、Floyd算法和0-1整数规划算法求解本题,因此要将地图转化为有向图或者无向图模型,因此首先要将地图上的数据整理为有(无)向图矩阵。我们能够利用matlab编程对数据进行整理。问题一的分析对于问题一,我们将问题抽象成一个有向图,每一个城市由一个标有数字的点代表(正如题中所示)。其中1代表起点伦敦,2～54代表沿途的城市,以55代表终点。将每段路径所需花费的时间记为该段路径的权值。由于题目规定只能向东移动,我们就将每条路径设为单向,并对地图进行整理以便整理相应的矩阵。由此,将问题抽象为最短路径问题模型。考虑到模型中每段路径的权值非负,能够用Dijkstra算法、Floyd算法和0-1整数规划算法,用matlab和lingo软件编程求解出最短环绕地球路径及对应的天数。问题二的分析对于问题二,我们首先以上海和纽约为起点(和终点),求出环绕地球的最短路径。再将问题推广:在哪些城市打赌自己能在80天内环游世界能赢?这样就能够很好地解答第二问。为此,我们根据Floyd算法,利用matlab编程,求出所有点的环绕地球最短天数。若此天数小于或等于80,说明从该城市出发,有可能在80天内环游地球,即打赌有可能赢;若此天数大于80,说明从该城市出发,不论走哪条路线都不可能在80天内环绕地球一周,即打赌必输。由此能够判断出从哪些城市出发有可能在80天内环绕地球一周,哪些城市不能。模型假设假设只能沿着题中网络图中的线路旅行,不能超出网络图的范围;假设图中每两个城市之间的行程(天数)真实可靠,且均为绝对时间,即客观地、仅表征两地之间距离的量度,而不存在时差;假设题目地图中并未标出的数字15与19,31与32所代表的两地之间的旅行时间分别和20与19、31和30的旅行时间成比例(做出此假设的依据是基于1872年能采用的旅行方式以及距离);假设主人公福格环游世界一周所用时间即为所选路径上各数字之和,即各段路程所用时间均取整数,而且其它任何因素对环游时间所造成的干扰均认为可忽略不计。符号说明P(u,v)从点u到点v的路径;w(P)路径上的边权之和称为该路径的权;P*(u,v)从u到v的路径中权最小者,从u到vd(u,v)Dijkstra算法中(u,v)路的最小权,u和v之间的距离;cijDijkstra算法中所有的边ij∈E(G)的非负边长D(k)[i][j]Floyd算法中从Vi到D(n-1)[i][j]Floyd算法中从Vi到Vj模型建立与求解根据问题的分析,我们首先对数据进行了预处理,再利用Dijkstra算法、Floyd算法和0-1整数规划算法,用matlab和lingo软件编程求解问题一和问题二。数据的预处理补全图中信息观察题中地图能够发现,城市Minsk(15)与Moscow(19)之间、Calcutta(31)与Bangkok(32)之间的行程没有给出。我们根据比例求出其之间的行程。我们认为,城市Minsk(15)与Moscow(19)之间的旅行方式跟城市Kiev(20)与Moscow(19)之间的旅行方式一样,粗略地认为这两段路径所花费的时间成比例。经过查看google地图,我们查到Minsk(15)与Moscow(19)之间的距离大约为705km,Kiev(20)与Moscow(19)之间的距离约为851km。计算得到Minsk(15)与Moscow(19)之间的行程大约为8天。同样,我们认为城市Calcutta(31)与Bangkok(32)之间的旅行方式跟城市Calcutta(31)与Madras(30)之间的旅行方式一样,为轮船,粗略地认为这两段路径所花费的时间成比例。经过查看google地图,我们查到Calcutta(31)与Bangkok(32)之间的距离大约为km,Calcutta(31)与Madras(30)之间的距离约为1709km。计算得到Calcutta(31)与Bangkok(32)之间的行程大约为4天。补全图中信息为了后面的计算,我们需要将网络地图抽象成为有向图模型。为此,我们将每一个城市由一个标有数字的点代表(正如题中所示)。其中1代表起点,2～54代表沿途的城市,以55代表终点。将每段路径所需花费的时间记为该段路径的权值。由于题目规定只能向东移动,我们就将每条路径设为单向。我们发现,除了19-20、54-1、53-2和52-2这四段路径,其它路劲均为小编号点指向大编号点,这一规律帮助我们整理出有向图模型(见附录一),能够应用于后面的算法。问题一模型的建立与求解我们首先建立出从伦敦出发回到伦敦的模型,利用Dijkstra算法、Floyd算法和0-1整数规划算法进行求解。问题一模型的建立图表SEQ图表\*ARABIC2从伦敦出发环绕地球一周的加权图表SEQ图表\*ARABIC2从伦敦出发环绕地球一周的加权图其中,1号代表伦敦,55号代表终点伦敦,这样,将问题转化为从点1到点55的最小”路径”问题。我们用Dijkstra算法、Floyd算法和0-1整数规划算法进行求解。设P(u,v)是加权图中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P)。从u到v的路径中权最小者P*(u,v)称为从u到vDijkstra算法Dijkstra算法是用来求解两点间最短路径的几个点方法。基本思路是采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径我们把(u,v)路的最小权称为u和v之间的距离,并记以d(u,v)。设S是V的真子集且u0∈S,并记T=V-S。若P=u0∙∙∙ui∙v是从u0到Td而且从u0到Td为避免重复并保留每一步的计算信息,在算法中,每个顶点v给以标号L(v)。它是du0,v的一个上界。开始时L(u0)=0,而v≠u0,则有L(L(u)=LDijkstra算法结束时,从u0到v0的最短距离由标号L(Dijkstra算法计算最短路径的算法具体如下:输入:向图G=(VG,E(G))有一个源顶点s和一个汇顶点t,以及对所有的边ij∈E(G)的非负边长输出:G中从s到t的最短路径的长度。第0步:从对每个顶点做临时标记L开始,做法如下:Ls=0,且对出s外所有的顶点第1步:找带有最小临时标记的顶点(如果有结,随机地取一个),使该标记变成永久标记,意即该标记不再改变。第2步:对每个没有永久标记可是又与带有永久标记的顶点相邻的顶点j,按如下方法计算一个新的临时标记:Lj=minL(重复第1步和第2步,直到所有的点都打上了永久标记为止。根据以上算法编程能够求出从伦敦出发环绕地球一周到伦敦的最短路径和相应的天数。Floyd算法弗洛伊德算法采用图的带权邻接矩阵存储结构。其基本思想是假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj,中间经过结点序号不大于0的最短路径,不大于1的最短路径,直到中间顶点序号不大于n-1的最短路径,从中选取最小值,即为算法具体如下:若从Vi到Vj有弧,则从Vi到Vj存在一条长度为弧上权值(arcsij)的路径,该路径不一定是最短路径,尚需进行n次试探。首先考虑从Vi到Vj经过中间顶点V0的路径(Vi,V0在此路径上再增加一个顶点V1,也就是说,如果(Vi,…,V1)和(V1,…,Vj)分别是当前找到的中间顶点序号不大于0的最短路径,那么,(Vi,…,V1…,Vj)就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短路径相比较,从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短路径。再增加一个顶点V2继续进行这个试探过程。一般情况下,若经过n次比较之后,最后求得的便是从Vi到Vj现定义一个n阶方阵序列:

D其中,D(4)上述公式中,D(k)[i][j]是从Vi到Vj的中间顶点序号不大于k的最短路径长度;D(n-1)[i][j]0-1整数规划算法将问题转化为规划问题。假设图有n个顶点,现需要求从顶点1到顶点n的最短路径。设决策变量为xij,当顶点1至顶点n的路上含弧(i,j)时,xij=1;否则xmins.t.根据以上算法编程利用lingo软件求解能够得到从伦敦出发回到伦敦的最短路径极其相应天数。问题一模型的求解dijkstra算法求解根据上面dijkstra算法编写matlab程序(见附录二),得到最短天数为79天,线路为:1→6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1图表图表SEQ图表\*ARABIC3从伦敦出发环绕地球一周的最短路径Floyd算法求解根据上面Floyd算法编写matlab程序(见附录三),得到最短天数为79天,线路为:1→6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1能够发现求得的路径与用dijkstra算法求解的结果完全一样,说明了两种方法的正确性与准确性。0-1整数规划算法求解根据上面0-1整数算法编写lingo程序(见附录四),得到最短天数为79天,线路为:1→6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1能够发现求得的路径与用dijkstra算法求解的结果完全一样,说明了两种方法的正确性与准确性。综上所述,从伦敦出发环绕地球一周所需最短时间为79天,小于80天。因此打赌有赢的希望。最佳线路,即为最短路径为:1→6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1线路图如图3。问题二模型的建立与求解考虑到编程和运算方便等因素,我们再一次利用Floyd算法对第二问进行求解。我们首先分别以Shanghai(37)和NewYork(53)两点为起点,编写matlab程序,得到最短路径分别为:以Shanghai(37)为起点:37→39→41→47→50→53→2→4→7→12→17→22→23→28→31→32→35→37最短天数为75天。以NewYork(53)为起点:53→2→4→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53最短天数为75天。可见,以Shanghai(37)或者NewYork(53)为起点环绕地球一周的最短路径相同,最短天数为75天,在这两点打赌均有赢的希望。具体路线图如下:图表SEQ图表\*ARABIC图表SEQ图表\*ARABIC4从Shanhai(37)或NewYork(53)为起点出发环绕地球一周的最短路径图我们又考虑到,在其它城市打赌,即以其它城市为起点,是否能在80天内环游世界。若将图中所有点的环游世界的最短路径极其相应天数求出,就能很轻易地判断出赌局是否能赢。在此,我们依然选用Floyd算法进行求解。进一步,我们考据到假若根据前面的方法,每一个起点都修改一次网络交通图,工程量巨大,而且容易出错。为此,将前面的算法稍微改进。我们考虑到Floyd算法能够处理有向图的带权邻接矩阵,我们将网络线路图抽象成为一个不给定起点的有向图(准确的说是有向环),以便在后面的编程中,不论以哪一个城市为起点,都能够用这个有向图对应的带权邻接矩阵(见附录五),即这个矩阵是每次运算求解共用的矩阵。同时,在之前的程序上加上一个循环,使得程序自动输出所有点作为起点时的最短线路和相应的天数。按照此方法编程(见附录六),得到分别以54个点为起点环游地球的最短路径极其相应的天数,如下表:表格SEQ表格\*ARABIC1以各点为起点环游世界的最短天数起点12345678910天数79757775767975769595起点11121314151617181920天数93757610098937510010798起点21222324252627282930天数9375759382100100758478起点31323334353637383940天数757577100759475947594起点41424344454647484950天数75818094949475867975起点51525354天数86787589其中,”起点”是指起点城市对应的序号,”天数”是指从该城市出发环绕地球一周所需要的最少天数。具体的每个点的最短路径见附录七。图表SEQ图表\*ARABIC5打赌有可能赢的城市由分析可知,若环游地球最短路径所对应的天数小于等于图表SEQ图表\*ARABIC5打赌有可能赢的城市在以上点代表的城市打赌有可能赢。模型检验与评价针对上述两个问题的模型的建立与求解是建立在模型假设成立的基础上的,然而在实际情况下,各假设不可能严格成立,如题目地图中所列出的任意两点之间的旅行天数不可能均为整数,不论使用何种交通方式都会存在一定的误差,另外在主人公福格的整个旅行期间不可能完全符合理想的环游时间,期间一定会有一些不可预知的因素。但同时,本模型以最大限度地模拟了真实情况,捕捉到了主要因素,并适时地忽略了次要因素及不可预知误差对模型求解造成的极其微弱的影响。模型检验经过对上述问题的分析,我们已得出了基本的结论,即:从伦敦出发再回到伦敦的最短环绕天数为79天,路径为:1->6->7->12->17->22->23->28->31->32->35->37->39->41->47->50->53->1。从纽约出发再回到纽约的最短环绕天数为75天,路径为:53->2->4->7->12->17->22->23->28->31->32->35->37->39->41->47->50->3.从上海出发再回到上海的最短环绕天数为75天,路径为:53->2->4->7->12->17->22->23->28->31->32->35->37->39->41->47->50->53.而且75天为环游世界所需要的最短天数(详见附录)。同时我们在求解第一个问时,我们同时利用了Dijkstra算法、Floyd算法和最短路径问题的0—1规划模型三种方法进行了平行求解并得到了完全相同的结论,这个过程同时也起到了模型检验的作用,从而使模型所求的结论更具可信性。之后,在第二问中,我们利用基于Floyd算法的Matlab编程改进方法所得的各点的结论与单独利用上述三种方法中的任意一种的方法所得的结论亦完全相同。这体现了模型建立的层进性和相互印证性。模型评价本模型经过Dijkstra算法、Floyd算法和最短路径问题的0—1规划模型等编程方法建立起的模型较好地达到了解决题设问题的目的。但同时亦有不足,即各假设不可能严格成立,如:15与19点,31与32点之间的旅行天数是基于1872年能采用的旅行方式以及距离所做出的估算,不可能完全模拟出当时的真实旅行天数。但这并没有影响本模型得出较正确的结论。本文主要有三个亮点:第一、在第一个问中同时利用三种方法进行平行求解,并得到了完全相同的结论,说明了模型的可靠性;第二、基于第一问中的Floyd算法,建立通用的有向图模型和带权邻接矩阵,方便而快速地求得了以任何一点为起点环游世界的最短路径及相应天数;第三、在第二个问的基础上,我们又对模型进行了推广,得到在不给定起点的条件下环游世界的最短路径。模型的改进为了消除在15-19和31-32两段因为人为估计导致距离不准确的误差,我们对这两段不同的值进行了研究。我们依然根据第二问中使用过的Floyd算法,利用matlab编程,设我们假设的这两段天数的误差在±2天之内,得到15-19和31-32之间天数取不同值时,各个点的最短径及相应的天数,并着重考虑打赌输赢情况改变的城市(具体的程序见附录八)。设i表示15-19路径需要的天数,j表示31-32路径所需要的天数。打赌输赢情况会发生变化的城市见下表:表格SEQ表格\*ARABIC2两段路径变化时打赌输赢情况变化的城市及相应最短天数的变化i=6,j=2i=6,j=3i=6,j=4城市原天数天数城市原天数天数城市原天数天数258280428180428179i=6,j=5i=6,j=6i=7,j=2城市原天数天数城市原天数天数城市原天数天数4380811798125828067981428179438082497981i=7,j=3i=7,j=4i=7,j=5城市原天数天数城市原天数天数城市原天数天数428180438081i=7,j=6i=8,j=2i=8,j=3城市原天数天数城市原天数天数城市原天数天数1798125828042818067981428179438082497981i=8,j=5i=8,j=6i=9,j=2城市原天数天数城市原天数天数城市原天数天数4380811798125828067981428180438082497981i=9,j=3i=9,j=4i=9,j=5城市原天数天数城市原天数天数城市原天数天数428180438081i=9,j=6i=10,j=2i=10,j=3城市原天数天数城市原天数天数城市原天数天数1798125828042818067981428180438082497981i=10,j=4i=10,j=5i=10,j=6城市原天数天数城市原天数天数城市原天数天数4380811798167981438082497981其中,”原天数”表示我们在问题二中求得的最短天数,”天数”表示在两段不确定路径取新值时新的环球最短天数。以上表中个点就是当15-19、31-32两段路径时间变化时,打赌输赢情况变化的城市。能够发现,当这两段路径所需时间发生变化时,只会影响到1、6、25、42、43、49这六个点的打赌输赢的变化。模型的推广与应用本模型是基于Dijkstra算法、Floyd算法及其改进的Matlab算法和最短路径问题的0—1规划模型方法所建立的数学模型。本模型在较好地解决了题设的两个问题外还得到了全球54个点中环游世界所需的最短天数。这一结论更具一般性,对于同类问题的研究具有指导意义。现举例如下:计算机管线的综合布置,对于大型的计算机群来说,计算机之间的联机方式在很程度上决定了计算机间信息交流与传递的速度。而大型的计算机群之间的分布和管线的长短可类比成题中的地图形式,从而利用本模型的方法与结论得到计算机间的最佳连接方式,既减少了成本,又提高了计算机间信息交流与传递的速度。最短路径问题在交通网络结构的分析,交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择,通讯线路的建造与维护,运输货流的最小成本分析,城公共交通网络的规划等,都有直接应用的价值。在实际中还常见于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内,在行车过程中还需要实时计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如,在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统,需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息;而当这些场合发生盗窃、抢劫等突发犯罪事件时,安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则能够达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时,将图论中Dijkstra算法应用于目标信息引导系统的设计中,经过Dijkstra算法,首先计算出任一指定位置点距各疏导出口的最短路径树,进而经过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示,从而达到优化目标引导路径的目的．按照城乡运输一体化的总体思路,为实现农村村村通客车的目标,针对农村客运线路繁杂,节点众多的特点,布局优化农村公路客运网的规划和建设是农村发展的重要内容,为落实贯彻中央l号文件,解决三农问题,全面建设小康社会,实现人便于行,货畅其流。需要从规划布局的角度,科学地审视农村公路网和客运线路。村村通客车,是农村客运网的基本要求,但农村村屯点多面广,线路繁杂,网络节点众多,道路迂回曲折。如何科学合理的选择路径,即达到农村客运网络畅达便捷,合理布局即是关键问题。现有的客运线路,系依托路网,村屯自然经济和区域特点,经经营者申报,交通运政管理部门审批而形成;其路径是否合理,线路覆盖和便捷程度,总体资源配置是否优化,尚无完整定量分析,系统和路网是否科学等一系列问题还有待确定。参考文献[1]贲可荣,袁景凌,高志华,离散数学,北京:清华大学出版社,

.3[2](美)吉奥丹诺等著,叶其孝等译,数学模型,北京:机械工业出版社,.8[3]卓金武,MATLAB在数学中的应用,北京:北京航空航天大学出版社,.2[4]傅鹂,龚劬,刘琼荪,何中市,《数学实验》,北京:科学出版社,.9[5]张绍民,李淑华,《数据结构教程C语言版》,北京:中国电力出版社,.6[6]鲍培明,距离寻优中Dijkstra算法的优化,计算机研究与发展,第38卷第3期:307-311,.3[7]蔡明山,求解电力系统潮流方程全部解的LINGO方法,长春工业大学学报(自然科学版),第28卷第3期:275-278,.9[8]李元臣,刘维群,基于Dijkstra算法的网络最短路径分析,微计算机应用,第25卷第3期:295-298,.5附录附录一起点终点权起点终点权起点终点权124172233439916118194353721931827203543281105192093638524219272337392233202412384042532027183941223522124103942263842223339432446322241440441247223258414735125232854248958324251242508674242615434966104252844445186114252964546971232629846217813226342446315910227342347494914228306475031011228314485151015429314495251019929342550525111553031350533111623033451544121733132451532131733133552531141843137315229151983233353110152043235453271620633355541716213333621721334375附录二Dijkstra算法的Matlab程序: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);附录三Floyd算法的Matlab程序:function[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;end附录四附录五附录六求各点最短路径的Matlab算法:clear;a=load('A.txt');%加载数据l=size(a,1);p=max(a);pn=max(p(1,1),p(1,2));%pn表示点标号的最大值w=inf*ones(pn,pn);%w表示所给图的带权邻接矩阵,初值为Inff=fopen('output.txt','w');%打开输出文件fori=1:l;%将各边的权值写入邻接矩阵w(a(i,1),a(i,2))=a(i,3);endfori=1:54;%对各点使用Floyd算法求最短路径[min1,path1]=floyd(w,i,i);min(i)=min1;fprintf(f,'PathofPoint%d:\n',i);%输出点i的最短路径forj=1:size(path1,2);if(j~=size(path1,2))fprintf(f,'%d->',path1(j));elsefprintf(f,'%d\n',path1(j));endendendfprintf(f,'\nThelongthofshortestpathofeverypoint:\n');fori=1:size(min,2);%按点标号递增序,每行5个,输出从各点出发环游世界的最少天数if(~mod(i,5))fprintf(f,'%4d\n',min(i));elsefprintf(f,'%4d',min(i));endendfclose(f);附录七从各点出发环游世界的最短路径:起点1:1→6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1起点2:2→4→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→2起点3:3→8→13→17→22→23→28→31→32→35→37→39→41→47→50→53→2→3起点4:4→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→2→4起点5:5→12→17→22→23→28→31→32→35→37→39→41→47→50→53→2→5起点6:6→7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→1→6起点7:7→12→17→22→23→28→31→32→35→37→39→41→47→50→53→2→4→7起点8:8→13→17→22→23→28→31→32→35→37→39→41→47→50→53→2→5→8起点9:9→10→11→16→21→24→25→28→31→32→35→37→39→41→47→50→53→1→9起点10:10→11→16→21→24→25→28→31→32→35→37→39→41→47→50→53→1→10起点11:11→16→21→24→25→28→31→32→35→37→39→41→47→50→53→1→6→11起点12:12→17→22→23→28→31→32→35→37→39→41→47→50→53→2→4→7→12起点13:13→17→22→23→28→31→32→35→37→39→41→47→50→53→2→5→8→13起点14:14→18→27→34→37→39→41→47→50→53→1→9→14起点15:15→20→24→25→28→31→32→35→37→39→41→47→50→53→1→10→15起点16:16→21→24→25→28→31→32→35→37→39→41→47→50→53→1→6→11→16起点17:17→22→23→28→31→32→35→37→39→41→47→50→53→2→4→7→12→17起点18:18→27→34→37→39→41→47→50→53→1→9→14→18起点19:19→27→34→37→39→41→47→50→53→1→9→14→18→19起点20:20→24→25→28→31→32→35→37→39→41→47→50→53→1→10→15→20起点21:21→24→25→28→31→32→35→37→39→41→47→50→53→1→6→11→16→21起点22:22→23→28→31→32→35→37→39→41→47→50→53→2→4→7→12→17→22起点23:23→28→31→32→35→37→39→41→47→50→53→2→4→7→12→17→22→23起点24:24→25→28→31→32→