基于Floyd算法与最短距离问题的分析.pdf

基于 Floyd 算法最短距离的问题分析 贺增增 武昌理工学院 摘要 本文主要是通过借助Floyd 算法来求解任意两点间的最短路问题，进而解 决货物最快运送，合理设立燃料补给点以及消防站的最佳选址问题。 针对问题一：问题一是有关最短运输路线问题，可以将该问题转化为求最 短距离对应的路径问题，利用Floyd 算法通过编程可以得到最快地到达目的地 的路径为v1  v8  v 9  v10  v11 。 针对问题二：本问题是要设计一个简易的公路建设方案，要求燃料补给点 到油库之间的公路建设花费最少，也即是燃料补给点到油库的距离最小。借助 Floyd 算法编程求解得到所有将要设立的燃料补给点到油库的最小距离和，最 后给出了7 个燃料补给点的修建方案图。 针对问题三：要求在已给出的10个消防重点单位中选择1个消防重点单位 设立消防站。通过Floyd 算法编程可以求解得到10 组消防重点单位到其它的消 防单位的距离，再分别取10 组中各自的最大距离作对比，得到其中最小值对应 的消防单位，最后确定了把消防单位 作为消防站的修建地。 v 8 一、问题重述 最短运输路线问题: 每条弧上的数字代表车辆在该路段行驶所需的时间， 有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1 号顶点运往 11 号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？ 简易公路建设方案: 某合同战术训练基地为保障即将进行的联合军事演习， 准备在原有的1个油库的基础上，再设立7 个固定的燃料补给点,为了使联合军 事演习正常进行，请为即将新建的7 个固定燃料补给点确定合理的修建地址。 消防站选址问题: 某城市的开发区中要建一个消防站,其中v , v , , v 表 1 2 10 示开发区中10个消防重点单位，考虑到交通路况，部分单位之间往返的距离不 完全相同，请帮助消防站做出合理的选址。 二、问题分析 对于问题一，若有一批货物要从1 号顶点运往11 号顶点，问运货车应沿哪 条线路行驶，才能最快地到达目的地？将问题简化为直接求1 号顶点到11顶点 的最短距离的路径。 1 对于问题二，设立燃料补给点需要考虑到，当联合军事演习的飞机或战车 没油时，补充燃料用掉的时间最短。而补充燃料的用时最短，无非就是燃料补 给点到油库的距离最短。现在要求设立七个固定燃料点，那么这七个燃料点必 须都满足到油库的距离最短，即各燃料点到油库的距离和最短。 对于问题三，在 10 个消防重点单位中，选择一个消防重点单位建立消防站， 应该考虑到当火灾发生时，消防站可以及时赶到火灾发生区，即消防站应到最 远的消防重点单位的距离也是最小的。可以将问题转化先求每个消防重点单位 到其它的消防单位的距离，取它们各自的最大距离作对比，然后得到其中最小 值对应的消防单位，最后确定把该消防单位作为消防站。 三、符号说明 A :邻接矩阵 D :距离矩阵 R :路径矩阵 四、模型建立与求解 1. 问题 1 模型——最短运输路线问题 (1)假设 1）假设运输路线交通网络图中数据都是准确的， 2）货车正常运输，不考虑意外情况的发生， 3）忽略在误差范围内的计算误差。 4）将运出地与运入地均理想化成点。 (2)模型 已知运输路线交通网络图如下所示： 2