足球比分直播

航空路线建模.doc

返回
航空路线建模.doc_第1页
第1页 / 共4页
航空路线建模.doc_第2页
第2页 / 共4页
航空路线建模.doc_第3页
第3页 / 共4页
航空路线建模.doc_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述:
航空路线建模问题重述某航空公司在 6 个城市 C1,,C6 中都有分公司,从 Ci到 Cj 的直达航班票价由下述矩阵的第 i 行、第 j 列元素给出( ∞ 表示无直达航班),试计算从 C1 出发到其他 5 个城市的最廉价路线。 ?????????????052510102425501014问题分析要求 c1 到 c5 的最廉价路线,即从 c1 出发到每个点的路径都最短。可用 Dijkstra 算法求固定起点的最短路问题。模型假设1.假设飞机在飞行过程中速度不变2.假设飞机正常飞行,不会发生突发事件以及天气变化等建立模型定义 d 为从 v1 到 vj 的当前“距离”Dijkstra 算法的过程就是不断更新 dvj,最终使得所有 dvj达到最小。W 表示图 G 的带权邻接矩阵,dvj表示从 v1 到 vj 的只允许经过已选出顶点的最短路的权。(1)令 dvjw1j, S{v1}, RV\S{v2,,vn}(2)在 R 中寻找一个顶点 vk,使得??????minjk jvRdvdv??置 SS∪{vk}, RV\S。若 R?,终止算法。(3)修正 dvj,对 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。即其路线模型图如下模型评价该模型能得到最短距离的路线图,具有普遍性,该模型求解简单实用性强,考虑到一些天气等因素,飞机需要更换路线,此模型需考虑更多因素。
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播