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

《基于Floyd算法与最短距离问题的分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于Floyd算法最短距离的问题分析贺增增武昌理工学院摘要本文主要是通过借助Floyd算法来求解任意两点间的最短路问题，进而解决货物最快运送，合理设立燃料补给点以及消防站的最佳选址问题。针对问题一：问题一是有关最短运输路线问题，可以将该问题转化为求最短距离对应的路径问题，利用Floyd算法通过编程可以得到最快地到达目的地的路径为vvvvv1891011。针对问题二：本问题是要设计一个简易的公路建设方案，要求燃料补给点到油库之间的公路建设花费最少，也即是燃料补给点到油库的距离最小。借助Floyd算法编程求解得到所有将要设立的燃料补给点到油

2、库的最小距离和，最后给出了7个燃料补给点的修建方案图。针对问题三：要求在已给出的10个消防重点单位中选择1个消防重点单位设立消防站。通过Floyd算法编程可以求解得到10组消防重点单位到其它的消防单位的距离，再分别取10组中各自的最大距离作对比，得到其中最小值对应的消防单位，最后确定了把消防单位v作为消防站的修建地。8一、问题重述最短运输路线问题:每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？简易公路建设方案:某合同战

3、术训练基地为保障即将进行的联合军事演习，准备在原有的1个油库的基础上，再设立7个固定的燃料补给点,为了使联合军事演习正常进行，请为即将新建的7个固定燃料补给点确定合理的修建地址。消防站选址问题:某城市的开发区中要建一个消防站,其中v,v,,v表1210示开发区中10个消防重点单位，考虑到交通路况，部分单位之间往返的距离不完全相同，请帮助消防站做出合理的选址。二、问题分析对于问题一，若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？将问题简化为直接求1号顶点到11顶点的最短距离的路径。对于问题二，设立燃料补

4、给点需要考虑到，当联合军事演习的飞机或战车没油时，补充燃料用掉的时间最短。而补充燃料的用时最短，无非就是燃料补给点到油库的距离最短。现在要求设立七个固定燃料点，那么这七个燃料点必须都满足到油库的距离最短，即各燃料点到油库的距离和最短。对于问题三，在10个消防重点单位中，选择一个消防重点单位建立消防站，应该考虑到当火灾发生时，消防站可以及时赶到火灾发生区，即消防站应到最远的消防重点单位的距离也是最小的。可以将问题转化先求每个消防重点单位到其它的消防单位的距离，取它们各自的最大距离作对比，然后得到其中最小值对应的消防单位，最后确定把该消防单位作为消

5、防站。三、符号说明A:邻接矩阵D:距离矩阵R:路径矩阵四、模型建立与求解1.问题1模型——最短运输路线问题(1)假设1）假设运输路线交通网络图中数据都是准确的，2）货车正常运输，不考虑意外情况的发生，3）忽略在误差范围内的计算误差。4）将运出地与运入地均理想化成点。(2)模型已知运输路线交通网络图如下所示：运输路线交通网络图由网络图可得邻接矩阵A如下08∞∞∞∞∞∞∞78∞∞03∞∞∞∞∞∞∞∞∞∞∞056∞∞∞5∞∞∞∞∞0∞∞1∞12∞∞∞∞6∞∞∞0210A=

6、∞∞∞∞∞∞∞2093∞∞∞∞∞∞∞∞∞908∞∞∞∞∞∞∞∞09∞∞∞∞∞∞∞7902∞∞∞∞∞∞∞∞202∞∞∞∞∞∞∞10∞∞∞通过matlab软件编程（源程序见附件1），借助Floyd算法求出距离矩阵D如下：081116171678171921310389118231416182836056852011131523317013121568102230611021114579D=

7、2028813209123572937172211902112141681619241618150911131725131879189024192715209112011202324016211012212415170求得路径矩阵如下：1222277888832333333333553455755555554555555566335636666R=99555679999

8、66666676666111199189998855555891010999999999101