基于Floyd算法建模的研究应用

柳雪飞 朱跃 邓敏英

（武汉生物工程学院湖北武汉４３０４１５）

摘要：对带权图中所有顶点之间的最短路问题，通常采用Ｆｌｏｙｄ算法．详细阐述了Ｆｌｏｙｄ算法的基本思想、求解步骤及一种简便的路径标记方法。通过实例讨论了Ｆｌｏｙｄ算法在实际生产生活如选址问题、高速公路收费系统中的应用。

教育期刊网 http://www.jyqkw.com
关键词 ：Ｆｌｏｙｄ算法；带权图；数学模型；最短路径

中图分类号：TP301.6 文献标识码：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６６５－２２７２．２０１5．07．００40

０引言

Ｆｌｏｙｄ算法是求解带权图中所有顶点对之间最短路问题的最有效的算法之一，这一算法在实际生产生活中经常遇到，因此，许多文献都对此算法作了介绍。通常的最短路径算法，都是建立在抽象的数学模型之上，即网络模型。本文将从图论中的带权图，用数学建模的方法来探讨Ｆｌｏｙｄ算法的原理、路径标记方法、及其应用。

１Ｆｌｏｙｄ算法描述

１．１基本思想

Ｆｌｏｙｄ算法是由弗洛伊德（Ｆｌｏｙｄ）提出的，又称为插点法，其基本思想是：

第一，设邻接矩阵W，其元素W［i］［j］为权值，若权值为∞，表示两点之间不存在直接连通弧。

例如在一个带权图中，设结点数为n(v1,v2,…，vn)，求从结点vi到vj的最短路径。若从到有连通弧，则存在一条路径，长度记为W［i］［j］的，但是不一定为最短路径，所以多数需要做n次试探。

第二，验证路径(vi , v1 , vj)的存在性（即弧(vi , v1)和v1 , vj的存在性）．若存在，则比较(vi , vj)和(vi , v1 , vj)的路径长度，其最短路径取法是序号不大于１，从vi到vj长度较短者的中间顶点；若再增加点v2，最短路径的选法将它和前面不大于１的最短路径相比较之后，从中选出中间顶点的序号不大于２的最短路径，继续增加一点v3，进行试探，依次做下去。

在通常情况下，若（ｖｉ，…，ｖｋ）和 （ｖｋ，…，ｖｊ）分别表示的是从ｖｉ到ｖｋ与从ｖｋ到ｖｊ的中间顶点序号不大于ｋ－１的最短路径，把已经得到的从ｖｉ到ｖｊ中间顶点序号不大于ｋ－１的最短路径和（ｖｉ，…，ｖｋ，…，ｖｊ）相比较，较短者就是从ｖｉ到ｖｊ的中间顶点的序号不大于ｋ的最短路径；类推下去，经历ｎ次比较后，最后可得从ｖｉ到ｖｊ的最短路径。按此方法，就可求得各对顶点间的最短路径；同时，在比较过程中利用一个动态数组ｐａｔｈ记载每次进行路径试探过程中获得最短路径的结点编号。

１．２基本步骤

有ｎ个顶点的一个带权图Ｇ， 从１到ｎ进行编号．设距离矩阵的初值为带权邻接矩阵Ｗ，即

Ｄ（０）＝（ｄｉｊ（０））ｎ×ｎ＝Ｗ

其中：ｄｉｉ＝０，ｉ＝１，２，…，ｎ；ｄｉｊ＝∞，当ｉ，ｊ之间没有边时．

对于无向图，Ｄ（０）是对称矩阵， ｄｉｊ＝ｄｊｉ．

Ｆｌｏｙｄ算法就是递推产生一个矩阵序列Ｄ（０），Ｄ（１），…，Ｄ（ｎ）。其中ｄｉｊ（ｋ）表示从顶点ｖｉ到顶点ｖｊ的路径上所经过的顶点序号不大于ｋ的最短路径长度．

第１步构造Ｄ（1）＝（ｄｉｊ（1））ｎ×ｎ，其中ｄｉｊ（１）＝ｍｉｎ｛ｄ（０）ｉｊ，ｄｉ１（０）＋ｄ１ｊ（０）｝是从ｖｉ到ｖｊ的只允许以ｖ１作为中间顶点的路径中最短路长度．

第２步构造Ｄ（2）＝（ｄｉｊ（2））ｎ×ｎ，其中ｄｉｊ（2）＝ｍｉｎ｛ｄ（1）ｉｊ，ｄｉ2（1）＋ｄ2ｊ（1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２作为中间顶点的路径中最短路长度．

第ｎ步构造Ｄ（ｎ）＝（ｄｉｊ（ｎ））ｎ×ｎ，其中ｄｉｊ（n）＝ｍｉｎ｛ｄ（n-1）ｉｊ，ｄｉn（n-1）＋ｄnｊ（n-1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２，…，ｖｎ作为中间点的所有路径中最短路的长度．

故Ｄ（ｎ）是距离矩阵，反映了所有顶点对之间的最短距离信息．

２Ｆｌｏｙｄ算法应用

２．１选址问题

当知晓了一些现有设施的地址，如果要进而在确定一些新设施的地址，这是选址问题的意思。但是大部分选址问题，依据现实情况，有时候只有少数个地址能选择，所以通常采用离散型法来进一步解决。而求对应网络中全部点对间的最短路便是解决离散型选址问题的关键。

例１配送中心是物流网路中举足轻重的结点，它不仅承载着多种物流功能，还越来越多地进行指挥调度、信息处理等重要的职能，是全部物流网络的关键所在．今考虑在某个城市建立一个物流配送网络．如果各需求点之间物流费用见图１，试择最佳配送中心。

解：首先，运用Ｆｌｏｙｄ算法构造距离矩阵．

由图１写出其初始带权邻接矩阵Ｄ（０）：

依次插入中间点，得距离矩阵：

其次，计算各顶点作为配送中心时的总费用C（vi）=

由计算知，ｖ１到其它点的费用和为Ｃ（ｖ１）＝７＋５＋３＋９＝２４．

同理，Ｃ（ｖ２）＝１９，Ｃ（ｖ３）＝１３， Ｃ（ｖ４）＝１５，Ｃ（ｖ５）＝２５．最后，求出顶点ｖｋ，使Ｃ（ｖｋ）＝ｍｉｎ｛Ｃ（ｖｉ）｝，则ｖｋ是最优的配送中心顶点。

上述结果比较得出，到其他各点的费用最小．所以，如果经济因素来说，ｖ３为配送中心是最佳的．

另外，本算法也适合动态多配送中心网络规划。例如如果出现故障或最短路径被紧急占用时，就能迅速决定最优的备用调配中心来满足客户需求。

２．２高速公路收费系统

伴随我国交通运输的快速发展，高速公路联网收费逐渐成为一个热点问题。其联网改造问题必须是一个地方高速公路的入网必须面对的关键。

例２某市高速公路目前的特点是一环四射，如图２所示，试构造联网收费系统的任意两点间的收费矩阵。

解：问题分析：计算任意两站点间的费用是本问题的关键。

模型假设：高速公路网络是一个无向图，图２中结点分布分别表示各个站点，数字则表示站点的编号，权值表示两点之间的长度，因此，欲求最小费用矩阵的计算，其实就是计算两点间的最短路径。

模型建立：由于公路的特点是一环四射，分开计算环路段和射线段．例如计算图中站点２０→１２的最小费用时，则能转化为计算２０→４，４→１，１→１２的３段最小费用矩阵，再合并起来。

（１）针对环状路网（图２中１→２→３→４→５→１），用Ｆｌｏｙｄ算法求任意两点间的最短路径．给出图的初始邻接矩阵

（２）对于射线网，它实际上是一棵树（如果某射线存在环，可将该环从树中分离，其余部分就不构成环）．可以使用在稀疏图中效率更高的进球两点间的最短路径的算法，如Ｊｏｈｎｓｏｎ算法。

（３）合并各段最短路径：在上述两步后，求出多个最短路径的矩阵，每一个对应１个环路段，１个射线段．合并方案是将两个矩阵合二为一：

其中A,B表示计算过的单个段中任意两结点间的最短路径．而C,D则表示跨段的最短路径，将上述３个路段相加便可以计算其路径和长度．

综合以上三点，可以得到本例中的费用矩阵为：

从矩阵中可以看出任意两点间的费用额，而且对结点较多的高速公路网络，当增加路网结点和路段信息发生变化时，若需要重新计算，Ｆｌｏｙｄ算法的效率也比较可观。

教育期刊网 http://www.jyqkw.com
参考文献

１胡桔州．Ｆｌｏｙｄ最短路径算法在配送中心选址中的应用［Ｊ］．湖南农业大学学报自然科学版，２００４（４）

２郭强．对Ｆｌｏｙｄ算法的两点注记［Ｊ］．运筹与管理，２００１（１）

３叶奇明、石世光．Ｆｌｏｙｄ算法的演示模型研究［Ｊ］．海南大学学报自然科学版，２００８，（１）

４黄贤英、李玉桃、张本强．最短路径搜索算法在高速公路收费系统中的应用［Ｊ］．重庆工学院学报（自然科学版），２００７（３）

５谢政．网络最优化［Ｍ］．上海：科学出版社，２０１５．

６陈雨婕．用图示法解析最短路径算法［Ｊ］．电脑知识与技术，２００７（２４）．

（责任编辑 梁工）