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

《基于floyd算法建模的研究应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于Floyd算法建模的研究应用柳雪飞朱跃邓敏英（武汉生物工程学院湖北武汉４３０４１５）摘要：对带权图中所有顶点之间的最短路问题，通常采用Ｆｌｏｙｄ算法．详细阐述了Ｆｌｏｙｄ算法的基本思想、求解步骤及一种简便的路径标记方法。通过实例讨论了Ｆｌｏｙｄ算法在实际生产生活如选址问题、高速公路收费系统中的应用。..关键词：Ｆｌｏｙｄ算法；带权图；数学模型；最短路径中图分类号：TP301.6文献标识码：Ａｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６６５－２２７２．２０１5．07．００40０引言Ｆｌｏｙｄ算法是求解带权图中所有顶点对之间最

2、短路问题的最有效的算法之一，这一算法在实际生产生活中经常遇到，因此，许多文献都对此算法作了介绍。通常的最短路径算法，都是建立在抽象的数学模型之上，即网络模型。本文将从图论中的带权图，用数学建模的方法来探讨Ｆｌｏｙｄ算法的原理、路径标记方法、及其应用。１Ｆｌｏｙｄ算法描述１．１基本思想Ｆｌｏｙｄ算法是由弗洛伊德（Ｆｌｏｙｄ）提出的，又称为插点法，其基本思想是：第一，设邻接矩阵W，其元素W［i］［j］为权值，若权值为∞，表示两点之间不存在直接连通弧。例如在一个带权图中，设结点数为n(v1,v2,…，vn)，求从结点vi到vj的最

3、短路径。若从到有连通弧，则存在一条路径，长度记为W［i］［j］的，但是不一定为最短路径，所以多数需要做n次试探。第二，验证路径(vi,v1,vj)的存在性（即弧(vi,v1)和v1,vj的存在性）．若存在，则比较(vi,vj)和(vi,v1,vj)的路径长度，其最短路径取法是序号不大于１，从vi到vj长度较短者的中间顶点；若再增加点v2，最短路径的选法将它和前面不大于１的最短路径相比较之后，从中选出中间顶点的序号不大于２的最短路径，继续增加一点v3，进行试探，依次做下去。在通常情况下，若（ｖｉ，…，ｖｋ）和（ｖｋ，…，ｖｊ）

4、分别表示的是从ｖｉ到ｖｋ与从ｖｋ到ｖｊ的中间顶点序号不大于ｋ－１的最短路径，把已经得到的从ｖｉ到ｖｊ中间顶点序号不大于ｋ－１的最短路径和（ｖｉ，…，ｖｋ，…，ｖｊ）相比较，较短者就是从ｖｉ到ｖｊ的中间顶点的序号不大于ｋ的最短路径；类推下去，经历ｎ次比较后，最后可得从ｖｉ到ｖｊ的最短路径。按此方法，就可求得各对顶点间的最短路径；同时，在比较过程中利用一个动态数组ｐａｔｈ记载每次进行路径试探过程中获得最短路径的结点编号。１．２基本步骤有ｎ个顶点的一个带权图Ｇ，从１到ｎ进行编号．设距离矩阵的初值为带权邻接矩阵Ｗ，即Ｄ（０）＝（ｄｉ

5、ｊ（０））ｎ×ｎ＝Ｗ其中：ｄｉｉ＝０，ｉ＝１，２，…，ｎ；ｄｉｊ＝∞，当ｉ，ｊ之间没有边时．对于无向图，Ｄ（０）是对称矩阵，ｄｉｊ＝ｄｊｉ．Ｆｌｏｙｄ算法就是递推产生一个矩阵序列Ｄ（０），Ｄ（１），…，Ｄ（ｎ）。其中ｄｉｊ（ｋ）表示从顶点ｖｉ到顶点ｖｊ的路径上所经过的顶点序号不大于ｋ的最短路径长度．第１步构造Ｄ（1）＝（ｄｉｊ（1））ｎ×ｎ，其中ｄｉｊ（１）＝ｍｉｎ｛ｄ（０）ｉｊ，ｄｉ１（０）＋ｄ１ｊ（０）｝是从ｖｉ到ｖｊ的只允许以ｖ１作为中间顶点的路径中最短路长度．第２步构造Ｄ（2）＝（ｄｉｊ（2））ｎ×ｎ，其中ｄｉｊ（2

6、）＝ｍｉｎ｛ｄ（1）ｉｊ，ｄｉ2（1）＋ｄ2ｊ（1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２作为中间顶点的路径中最短路长度．第ｎ步构造Ｄ（ｎ）＝（ｄｉｊ（ｎ））ｎ×ｎ，其中ｄｉｊ（n）＝ｍｉｎ｛ｄ（n-1）ｉｊ，ｄｉn（n-1）＋ｄnｊ（n-1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２，…，ｖｎ作为中间点的所有路径中最短路的长度．故Ｄ（ｎ）是距离矩阵，反映了所有顶点对之间的最短距离信息．２Ｆｌｏｙｄ算法应用２．１选址问题当知晓了一些现有设施的地址，如果要进而在确定一些新设施的地址，这是选址问题的意思。但是大部分选址问题，依据现实情况

7、，有时候只有少数个地址能选择，所以通常采用离散型法来进一步解决。而求对应网络中全部点对间的最短路便是解决离散型选址问题的关键。例１配送中心是物流网路中举足轻重的结点，它不仅承载着多种物流功能，还越来越多地进行指挥调度、信息处理等重要的职能，是全部物流网络的关键所在．今考虑在某个城市建立一个物流配送网络．如果各需求点之间物流费用见图１，试择最佳配送中心。解：首先，运用Ｆｌｏｙｄ算法构造距离矩阵．由图１写出其初始带权邻接矩阵Ｄ（０）：依次插入中间点，得距离矩阵：其次，计算各顶点作为配送中心时的总费用C（vi）=由计算知，ｖ１到其

8、它点的费用和为Ｃ（ｖ１）＝７＋５＋３＋９＝２４．同理，Ｃ（ｖ２）＝１９，Ｃ（ｖ３）＝１３，Ｃ（ｖ４）＝１５，Ｃ（ｖ５）＝２５．最后，求出顶点ｖｋ，使Ｃ（ｖｋ）＝ｍｉｎ｛Ｃ（ｖｉ）｝，则ｖｋ是最优的配送中心顶点。上述结果比较得出，到其他各点的费用最小．所以，如果经济因素来说，ｖ３为配送中心是