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

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

贺增增 武昌理工学院

摘要

本文主要是通过借助Floyd算法来求解任意两点间的最短路问题，进而解决货物最快运送，合理设立燃料补给点以及消防站的最佳选址问题。 针对问题一：问题一是有关最短运输路线问题，可以将该问题转化为求最短距离对应的路径问题，利用Floyd算法通过编程可以得到最快地到达目的地的路径为v1v8v9v10v11。

针对问题二：本问题是要设计一个简易的公路建设方案，要求燃料补给点到油库之间的公路建设花费最少，也即是燃料补给点到油库的距离最小。借助Floyd算法编程求解得到所有将要设立的燃料补给点到油库的最小距离和，最后给出了7个燃料补给点的修建方案图。

针对问题三：要求在已给出的10个消防重点单位中选择1个消防重点单位设立消防站。通过Floyd算法编程可以求解得到10组消防重点单位到其它的消防单位的距离，再分别取10组中各自的最大距离作对比，得到其中最小值对应的消防单位，最后确定了把消防单位v8作为消防站的修建地。

一、问题重述

最短运输路线问题: 每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？

简易公路建设方案: 某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的1个油库的基础上，再设立7个固定的燃料补给点,为了使联合军事演习正常进行，请为即将新建的7个固定燃料补给点确定合理的修建地址。 消防站选址问题: 某城市的开发区中要建一个消防站,其中v1,v2,L,v10表示开发区中10个消防重点单位，考虑到交通路况，部分单位之间往返的距离不完全相同，请帮助消防站做出合理的选址。

二、问题分析

对于问题一，若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？将问题简化为直接求1号顶点到11顶点的最短距离的路径。

1

对于问题二，设立燃料补给点需要考虑到，当联合军事演习的飞机或战车没油时，补充燃料用掉的时间最短。而补充燃料的用时最短，无非就是燃料补给点到油库的距离最短。现在要求设立七个固定燃料点，那么这七个燃料点必须都满足到油库的距离最短，即各燃料点到油库的距离和最短。

对于问题三，在10个消防重点单位中，选择一个消防重点单位建立消防站，应该考虑到当火灾发生时，消防站可以及时赶到火灾发生区，即消防站应到最远的消防重点单位的距离也是最小的。可以将问题转化先求每个消防重点单位到其它的消防单位的距离，取它们各自的最大距离作对比，然后得到其中最小值对应的消防单位，最后确定把该消防单位作为消防站。

三、符号说明

A:邻接矩阵 D:距离矩阵 R:路径矩阵

四、模型建立与求解

1. 问题1 模型——最短运输路线问题 (1)假设

1）假设运输路线交通网络图中数据都是准确的， 2）货车正常运输，不考虑意外情况的发生， 3）忽略在误差范围内的计算误差。 4）将运出地与运入地均理想化成点。 (2)模型

已知运输路线交通网络图如下所示：

2

运输路线交通网络图

由网络图可得邻接矩阵A如下

骣0???∞????∞????∞???∞???∞A=????∞????8????∞???∞????∞?桫80∞∞∞∞∞∞∞∞∞∞30∞6∞∞∞∞∞∞∞∞50∞∞∞∞∞∞∞∞∞6102∞∞7∞10∞∞∞∞209∞∞∞∞7∞5∞∞90∞∞∞∞8∞∞∞∞∞∞09∞∞∞∞∞∞∞3∞902∞∞∞∞∞∞∞∞∞20∞∞÷÷÷∞÷÷÷÷∞÷÷÷÷12÷÷÷÷10÷÷÷÷∞÷ ÷÷÷∞÷÷÷÷∞÷÷÷÷÷∞÷÷÷÷2÷÷÷÷∞÷通过matlab软件编程（源程序见附件1），借助Floyd算法求出距离矩阵D

如下：

?0???31????28????23???22???20D=????29????8????17???19?????è328036313028371625274011307681719131516161716788911823568520013121511021114132224182021211167910091891112901518202112210911241714116521?÷÷÷18÷÷÷÷15÷÷÷÷10÷÷÷÷9÷÷÷÷357÷ ÷÷÷121416÷÷÷÷91113÷÷÷÷÷024÷÷÷÷202÷÷÷÷15170÷?19161387求得路径矩阵如下：

3

骣1???3????5????5???6???9R=????6????1????8???9????5?桫225569618952335356159523443561595235555695957355666959573753771595÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷9999÷ ÷÷÷6666÷÷÷÷8999÷÷÷÷÷891010÷÷÷÷991011÷÷÷÷55511÷83556835568355683556（3）结果解释与分析

1号顶点到11号顶点的距离对应的距离矩阵D的第1行第11列即R111， ,而d111，因此说明1号顶点到11 顶点的最短距离为21，由路径矩阵R中,=21r1,11=8可知，1号顶点到11号之间插入了8号顶点，由r1,8=8可知1号顶点到8号顶点之间没有值插入，由r8,11=9可知8号顶点到11号之间插入了9号顶点，由r8,9=9可知8号顶点到9号顶点之间没有值插入，由r9,11=10可知9号顶点到11号之间插入了10号顶点，r9,10=10可知9号顶点到10号顶点之间没有值插入，r10,11=11可知10号顶点到11号顶点之间没有值插入。 综上所述可以得到最短距离的路径 即：18

91011

2. 问题2 模型——简易公路建设方案 （1）假设

1）假设公路花费图给出的数据都是真实有效的， 2）忽略在误差范围内的计算误差。

3）仅仅只考虑已给定的花费，忽略其他的费用。 4）将油库与燃料补给点均理想化成点。

4

（2）模型

记油库为v1，并记7个燃料补给点分别为v2，v3，v4，v5，v6，v7，v8。修建公路花费图如下所示：

修建公路花费图

由公路花费图可写出邻接矩阵A如下

骣0???1????2????∞?A=??7????4???8????∞?桫1023∞∞7∞2∞748∞÷÷÷23∞∞7∞÷÷÷÷015∞∞∞÷÷÷÷103∞∞6÷÷÷÷ 5303∞4÷÷÷÷∞∞3026÷÷÷÷∞∞∞204÷÷÷÷∞64640÷÷通过matlab软件编程（源程序见附件2），借助Floyd算法求出距离矩阵D如

下：

骣0???1????2????3?D=??6????4???6????9?桫求得路径矩阵R如下：

1236469÷÷÷0236579÷÷÷÷2014687÷÷÷÷3103686÷÷÷÷ 6430354÷÷÷÷5663026÷÷÷÷7885204÷÷÷÷9764640÷÷5

本文来源：https://www.bwwdw.com/article/90o5.html