导航菜单

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

柳雪飞 朱跃 邓敏英

(武汉生物工程学院湖北武汉430415)

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

教育期刊网 http://www.jyqkw.com
关键词 :Floyd算法;带权图;数学模型;最短路径

中图分类号:TP301.6 文献标识码:A doi:10.3969/j.issn.1665-2272.2015.07.0040

0引言

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

1Floyd算法描述

1.1基本思想

Floyd算法是由弗洛伊德(Floyd)提出的,又称为插点法,其基本思想是:

第一,设邻接矩阵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)的路径长度,其最短路径取法是序号不大于1,从vi到vj长度较短者的中间顶点;若再增加点v2,最短路径的选法将它和前面不大于1的最短路径相比较之后,从中选出中间顶点的序号不大于2的最短路径,继续增加一点v3,进行试探,依次做下去。

在通常情况下,若(vi,…,vk)和 (vk,…,vj)分别表示的是从vi到vk与从vk到vj的中间顶点序号不大于k-1的最短路径,把已经得到的从vi到vj中间顶点序号不大于k-1的最短路径和(vi,…,vk,…,vj)相比较,较短者就是从vi到vj的中间顶点的序号不大于k的最短路径;类推下去,经历n次比较后,最后可得从vi到vj的最短路径。按此方法,就可求得各对顶点间的最短路径;同时,在比较过程中利用一个动态数组path记载每次进行路径试探过程中获得最短路径的结点编号。

1.2基本步骤

有n个顶点的一个带权图G, 从1到n进行编号.设距离矩阵的初值为带权邻接矩阵W,即

D(0)=(dij(0))n×n=W

其中:dii=0,i=1,2,…,n;dij=∞,当i,j之间没有边时.

对于无向图,D(0)是对称矩阵, dij=dji.

Floyd算法就是递推产生一个矩阵序列D(0),D(1),…,D(n)。其中dij(k)表示从顶点vi到顶点vj的路径上所经过的顶点序号不大于k的最短路径长度.

第1步构造D(1)=(dij(1))n×n,其中dij(1)=min{d(0)ij,di1(0)+d1j(0)}是从vi到vj的只允许以v1作为中间顶点的路径中最短路长度.

第2步构造D(2)=(dij(2))n×n,其中dij(2)=min{d(1)ij,di2(1)+d2j(1)}是从vi到vj的只允许以v1,v2作为中间顶点的路径中最短路长度.

第n步构造D(n)=(dij(n))n×n,其中dij(n)=min{d(n-1)ij,din(n-1)+dnj(n-1)}是从vi到vj的只允许以v1,v2,…,vn作为中间点的所有路径中最短路的长度.

故D(n)是距离矩阵,反映了所有顶点对之间的最短距离信息.

2Floyd算法应用

2.1选址问题

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

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

解:首先,运用Floyd算法构造距离矩阵.

由图1写出其初始带权邻接矩阵D(0):

依次插入中间点,得距离矩阵:

其次,计算各顶点作为配送中心时的总费用C(vi)=

由计算知,v1到其它点的费用和为C(v1)=7+5+3+9=24.

同理,C(v2)=19,C(v3)=13, C(v4)=15,C(v5)=25.最后,求出顶点vk,使C(vk)=min{C(vi)},则vk是最优的配送中心顶点。

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

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

2.2高速公路收费系统

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

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

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

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

模型建立:由于公路的特点是一环四射,分开计算环路段和射线段.例如计算图中站点20→12的最小费用时,则能转化为计算20→4,4→1,1→12的3段最小费用矩阵,再合并起来。

(1)针对环状路网(图2中1→2→3→4→5→1),用Floyd算法求任意两点间的最短路径.给出图的初始邻接矩阵

(2)对于射线网,它实际上是一棵树(如果某射线存在环,可将该环从树中分离,其余部分就不构成环).可以使用在稀疏图中效率更高的进球两点间的最短路径的算法,如Johnson算法。

(3)合并各段最短路径:在上述两步后,求出多个最短路径的矩阵,每一个对应1个环路段,1个射线段.合并方案是将两个矩阵合二为一:

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

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

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

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

1胡桔州.Floyd最短路径算法在配送中心选址中的应用[J].湖南农业大学学报自然科学版,2004(4)

2郭强.对Floyd算法的两点注记[J].运筹与管理,2001(1)

3叶奇明、石世光.Floyd算法的演示模型研究[J].海南大学学报自然科学版,2008,(1)

4黄贤英、李玉桃、张本强.最短路径搜索算法在高速公路收费系统中的应用[J].重庆工学院学报(自然科学版),2007(3)

5谢政.网络最优化[M].上海:科学出版社,2015.

6陈雨婕.用图示法解析最短路径算法[J].电脑知识与技术,2007(24).

(责任编辑 梁工)

下载文本