1、航空路线建模问题重述:某航空公司在 6 个城市 C1,C6 中都有分公司,从 Ci到 Cj 的直达航班票价由下述矩阵的第 i 行、第 j 列元素给出( 表示无直达航班),试计算从 C1 出发到其他 5 个城市的最廉价路线。 052510102425501014问题分析:要求 c1 到 c5 的最廉价路线,即从 c1 出发到每个点的路径都最短。可用 Dijkstra 算法求固定起点的最短路问题。模型假设:1.假设飞机在飞行过程中速度不变2.假设飞机正常飞行,不会发生突发事件以及天气变化等建立模型:定义 d 为从 v1 到 vj 的当前“距离”Dijkstra 算法的过程就是不断更新 d(vj),
2、最终使得所有 d(vj)达到最小。W 表示图 G 的带权邻接矩阵,d(vj)表示从 v1 到 vj 的只允许经过已选出顶点的最短路的权。(1)令 d(vj)=w1j, S=v1, R=VS=v2,vn(2)在 R 中寻找一个顶点 vk,使得minjk jvRdvdv置 S=Svk, R=VS。若 R=,终止算法。(3)修正 d(vj),对 R 中的每个 vj,令min,j jkkjdvdvw转回(2)dC1 C2 C3 C4 C5 C650 35 25 1035 45 35 2535 45 3535 4545其模型图为:模型求解:求解的 c1 到 c5 的最短距离为 25,c1 到 c6 的最短距离为10;c1 到 c2 的最短距离为 35;c1 到 c4 最短距离为35;c1 到 c5 的最短距离为 25;c1 到 c3 的最短距离为45。即其路线模型图如下:模型评价:该模型能得到最短距离的路线图,具有普遍性,该模型求解简单实用性强,考虑到一些天气等因素,飞机需要更换路线,此模型需考虑更多因素。