最短航程问题

题目

某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（?表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。

?050?402510?

?5001520?25?

??

??1501020??

?? ?40201001025? ?25?2010055?

?? 1025?25550??

摘要

改革开发以来，我国的经济发展迅速，人民生活水平逐渐提高，2010年，我国GDP超越日本，排名世界第二。我国经济的发展，使人们对交通运输提出越来越多的需求， 而民航作为航空运输工具，在交通工具中起到十分重要的作用，新型飞机(民用)快速、续航能力强、安全、便捷的特点受到越来越多的人青睐。如果从交错复杂的飞机线路中找到最廉价的线路，不仅减少了中途时间，而且大大节省了开支费用，为企业和个人带来可观的经济效益。本文从航班网络的实际特点出发，对航班线路网和票价进行分析，将最佳路径搜索问题转化为图论中的最短路径的问题，通过对最短路径算法的分析，实现了Floyd算法求航班网络中的最短路径，将之建立模型，并描述了用matlab程序进行求解的过程。

关键词：最短路 matlab Floyd算法

问题提出

某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（?表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。

问题分析

若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。

题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。（此两点为主要约束条件）

我们确定本题为全局最短路问题，并采用Floyd算法，具体原理如下： （1） 求距离矩阵的方法

根据路线及票价表建立带权矩阵W，并把带权邻接矩阵我w作为距离矩阵的初始值，即D(0)?(dij(0))v?v?W

1.D?1??(dij(1))v?v，其中dij1?min?dij(0),di1(0)?d1j(0)?，dij(1)是从vi到vj的只允许以v1作为中间点的路径中最短路的长度。

2. D?2??(dij(2))v?v，其中dij2?min?dij(1),di2(1)?d2j(1)?，dij(2)是从vi到vj的只允许以v1，v2作为中间点的路径中最短路的长度。

……

vD(v)?(dij(v)?min?dij(v?1),dij(v?1)?dvj(v?1)?,dij(v)是从vi到vj的只允许v1、

v2、……、vv作为中间点的路径中最短路的长度。即是从vi到vj中间可插入如何顶点的路径中最短路的长度，因此D(v)即是距离矩阵。

（2） 求路径矩阵的方法

在建立距离矩阵的同时可建立路径矩阵R，R?(rij)v?v，rij的含义是从vi到vj的最短路径要经过点号为rij的点。

R(0)?(rij(0))v?v,rij(0)?j

每求得一个D(k)时，按下列方式产生相应的新的R(k)：

(k?1)(k?1)?kd,若 d?d?dijikkj?rij(k)??(k?1)

??rij,否则即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求得D(k)时求得R(k)，可由R(v)来查找任何点对之间最短的路径。

（3） 查找最短路径的方法

若rij(v)?p1，则点p1是点i到j的最短距离的中间点，然后用同样的方法再分头查找。若：

1. 向点i追溯得：rip1(v)?p2,rip2(v)?p3,...,ripk(v)?pk

2. 向点j追溯得：rp1j(v)?q1,rq1j(v)?q2,...,rqmj(v)?j

则由点i到j的最短路的路径为：i，pk,…,p2，p1，q1，q2，…,qm，j。

模型假设

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 35

10 25 35 25 35 0 path =

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 6

D便是最廉价的航费表，要求飞行路线，由path矩阵可以得到，比如2到5的路线：path(2,5)=4, path(4,5)=5,因此，应为2→4 →5

1：本文把所解决的问题归结为最短路问题，建立的数学模型清晰合理。 2：运用MATLAB软件处理数据和进行运算，降低运算量，简单易行，有很大的可操作性。且所得数据较为合理可靠。

3：在实际运用本方案中还应考虑自然因素对飞机航行的影响，还需根据实际情况进行灵活改变。

本文来源：https://www.bwwdw.com/article/nsug.html