航空路线建模---副本.docxVIP

航空路线建模0问题重述某航空公司在6个城市C1,…,C6中都有分公司，从Ci到Cj的直达航班票价由下述矩阵的第i行、第j列元素给出（?∞?表示无直达航班），试计算从C1出发到其他5个城市的最廉价路线。1问题分析要求c1到c5的最廉价路线，即从c1出发到每个点的路径都最短。可用Dijkstra算法求固定起点的最短路问题。?2模型假设1.各城市间的飞机线路固定不变 2.各城市间飞机线路的票价不改变 3.忽略乘客除票价以外的各项开销费用 4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。5.假设飞机在飞行过程中速度不变?3建立模型定义d为从v1到vj的当前“距离”Dijkstra算法的过程就是不断更新d(vj)，最终使得所有d(vj)达到最小。?Q表示图G的带权邻接矩阵，d(vj)表示从v1到vj的只允许经过已选出顶点的最短路的权。?（1）令d(vj)=w1j, S={v1}, R=V\S={v2,…,vn}（2）在R中寻找一个顶点vk，使得置S=S∪{vk}， R=V\S。若R=?，终止算法。（3）修正d(vj)，对R中的每个vj，令转回（2）模型图为：?4模型求解求解:c1到c5的最短距离为25，c1到c6的最短距离为10c1到c2的最短距离为35c1到c4最短距离为35c1到c3的最短距离为45?即其路线模型图如下：?