最短航程问题

题目 某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 摘要改革开发以来，我国的经济发展迅速，人民生活水平逐渐提高，2010年，我国GDP超越日本，排名世界第二。我国经济的发展，使人们对交通运输提出越来越多的需求， 而民航作为航空运输工具，在交通工具中起到十分重要的作用，新型飞机(民用)快速、续航能力强、安全、便捷的特点受到越来越多的人青睐。如果从交错复杂的飞机线路中找到最廉价的线路，不仅减少了中途时间，而且大大节省了开支费用，为企业和个人带来可观的经济效益。本文从航班网络的实际特点出发，对航班线路网和票价进行分析，将最佳路径搜索问题转化为图论中的最短路径的问题，通过对最短路径算法的分析，实现了Floyd算法求航班网络中的最短路径，将之建立模型，并描述了用matlab程序进行求解的过程。关键词：最短路 matlab Floyd算法问题提出某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 问题分析若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题求图中所有的最短路径。题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。（此两点为主要约束条件）我们确定本题为全局最短路问题，并采用Floyd算法，具体原理如下：（1） 求距离矩阵的方法根据路线及票价表建立带权矩阵，并把带权邻接矩阵我w作为距离矩阵的初始值，即1.，其中，是从到的只允许以作为中间点的路径中最短路的长度。2. ，其中，是从到的只允许以，作为中间点的路径中最短路的长度。,是从到的只允许、作为中间点的路径中最短路的长度。即是从到中间可插入如何顶点的路径中最短路的长度，因此即是距离矩阵。（2） 求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵，的含义是从到的最短路径要经过点号为的点。每求得一个时，按下列方式产生相应的新的：即当被插入任何两点间的最短路径时，被记录在中，依次求得时求得，可由来查找任何点对之间最短的路径。（3） 查找最短路径的方法若，则点是点到的最短距离的中间点，然后用同样的方法再分头查找。若：1. 向点追溯得：2. 向点追溯得：则由点到的最短路的路径为：，,，,，。模型假设a.各城市间的飞机线路固定不变b.各城市间飞机线路的票价不改变c.忽略乘客除票价以外的各项开销费用d.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。模型建立建立脚本m文件如下：w= 0,50,inf,40,25,10; 50,0,15,20,inf,25;inf,15,0,10,20,inf;40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0;D, path=floyd(a)模型求解运行便可输出结果。 D = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 3510 25 35 25 35 0path = 1 6 5 5 5 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 6 1 4 3 4 5 1 1 2 4 4 1 6D便是最廉价的航费表，要求飞行路线，由path矩阵可以得到，比如2到5的路线：path(2,5)=4, path(4,5)=5,因此，应为24 51：本文把所解决的问题归结为最短路问题，建立的数学模型清晰合理。2：运用M