为主要约束条件)РFloyd算法,具体原理如下:Р我们确定本题为全局最短路问题,并采用求距离矩阵的方法Р根据路线及票价表建立带权矩阵,并把带权邻接矩阵我w作为距离矩阵的初始值,即Р(2)求路径矩阵的方法Р在建立距离矩阵的同时可建立路径矩阵,,的含义是从到的最短路径要经过点号为的点。Р(3)查找最短路径的方法Р若,则点是点到的最短距离的中间点,然后用同样的方法再分头查找。Р三、模型假设:Р 1.各城市间的飞机线路固定不变Р 2.各城市间飞机线路的票价不改变Р 3.忽略乘客除票价以外的各项开销费用Р 4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。Р模型建立Р 建立带权邻接矩阵:Р 根据飞机路线及票价表建立带权邻接矩阵, 在带权邻接矩阵中用插入顶点的方法依次构造出 6 个矩阵。Р 采用floyd算法步骤为:Р:到的最短距离Р:到之间的插入点Р输入带权邻接距阵Р赋初值:对所有Р更新,:对所有,若,则Р ,.Р若,停止;否则,转(2).Р Р 运行程序得: Р D (1) Р D (2) 、Р D(3)、Р D (4) 、Р D( 5)、Р D(6),Р使最后得到的矩阵 D ( 6 ) 为飞机的最廉价矩阵。Р模型求解结果Р 根据模型求解,分析得出任意两个城市之间最廉价线路及票价为:Р C1→C2: 1→6→2;35?Р C1→C3:1→5→3,1→6→4→3;45?Р C1→C4:1→6→4,1→5→4﹔35Р C1→C5∶1→5﹔25Р C1→C6:1→6﹔10Р C2→C3∶2→3﹔15Р C2→C4∶2→4﹔20Р C2→C5∶2→4→5﹔30Р C2→C6∶2→5﹔25Р C3→C4∶3→4﹔10Р C3→C5∶3→5∶3→4→5﹔20Р C3→C6∶3→4→6﹔35Р C4→C5∶4→5﹔10Р C4→C6∶4→6﹔25Р C5→C6∶5→4→6﹔35
全文预览
