任意两个城市之间最廉价路线

《任意两个城市之间最廉价路线》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南阳师范学院2012年第四届数学建模竞赛论文答卷编号：（队伍编号）论文题目：任意两个城市之间最廉价路线参赛队员：1.姓名：王亚萍学院：物理与电子工程学院班级：10.2电话：152360715512.姓名:赵玉洁学院：物理与电子工程学院班级：10.1电话：152360791023.姓名：王菲学院：数学与统计学院班级：10.3电话：15236057605任意两个城市之间最廉价路线摘要关键词一、问题重述某公司在六个城市都有分公司，从到的直达航班票价由下述矩阵的第行,第列元素给出(表示无直达航班),请帮助该公司算出一张任意两个城市之间最廉价路线

2、表格.城市间直达航班票价矩阵已给出（相关数据查看原题）。二、问题分析根据题意可知任意两个城市之间的直达航班票价在往返之间是相同的，且是求任意两城市间的最短路问题，因此我们运用图论的知识中floyd算法来求解。三、模型假设1﹑假设每个城市间的票价是不随节日或其他影响而改变。2﹑假设该公司人员从一个城市到另一城市乘坐飞机过程中不返航。3﹑假设每个城市机场正常运营，各个航班不因天气变化或其他什么原因而延误。四、符号说明及概念引入:表示城市间直达航班票价矩阵，即初始带权的邻接矩阵：表示第n次插值后所得的距离矩阵:表示初始的城市间的路径矩阵：第n

3、次插值后所得的路径矩阵五、模型的建立与求解1）解题过程：把六个城市从到的直达航班票价由下述矩阵的第行,第列元素给出城市间直达航班票价矩阵转化为如图一的带权图：则初始带权的邻接矩阵为，初始的城市间的路径矩阵为，由Floyd算法：求任意两顶点间的最短路.d(i,j)：i到j的距离．r(i,j)：i到j之间的插入点．输入:带权邻接矩阵(1)赋初值：对所有i,j,d(i,j)w(i,j),r(i,j)j,k1.(2)更新d(i,j),r(i,j):对所有i,j，若d(i,k)+d(k,j)

4、,r(i,j)k(3)若k=，停止．否则kk+1，转(2)．得插入后，得，，插入后，得，插入后，得，插入后，，其中和的值均有两个，即两种情况都可以，以下情况相同。插入后，得插入后，得2）结果分析:由于一个城市到另一个城市是无向的，因而在此我们就考虑一个方向。由第六次插值后所得的距离矩阵和城市间的路径矩阵可得以下结果：1>从的最短路：，即从到需要经过，如图（加粗的边即是从一顶点到另一顶点所要经过的边，以下图像相同）：2>从的最短路：，即从到需要经过，如图：3>从的最短路：或，即从到需要经过或从到需要经过,如图:4>从的最短路：,如图:5>

5、从的最短路：,如图:6>从的最短路：,如图:7>从的最短路：,如图:8>从的最短路：,即从到需要经过,如图:9>从的最短路：,如图:10>从的最短路：,如图:11>从的最短路：或,如图:12>从的最短路：,即从到需要经过,如图:13>从的最短路：,如图:14>从的最短路：,如图:15>从的最短路：或,如图: