用Excel演示Floyd算法

楼建华

【摘 要】Floyd算法是计算最短路径长度的基本算法之一,若用Excel实现,算法的核心部分只需填写一个公式,比通常的四重循环结构算法简单、直观. 【期刊名称】《兵团教育学院学报》 【年(卷),期】2010(020)006 【总页数】3页(P50-52)

【关键词】Excel;演示;最短路径长度;Floyd算法 【作 者】楼建华

【作者单位】石河子大学信息科学与技术学院,,石河子市,832003 【正文语种】中 文 【中图分类】TP317.3

最短路径(长度)是图论、数据结构、运筹学等课程中的典型问题,Floyd算法是解决此类问题的基本算法之一。

Floyd算法的基本原理:如果顶点 vi到顶点 vj的某条最短路径经过顶点 vk,则 vi到 vk和 vk到 vj的最短路径共同组成 vi到 vj的一条最短路径。 Floyd算法的基本步骤:对邻接矩阵 (aij)n×n重复做下述迭代

aij=min{aik+akj|k=1,2,…,n}i,j=1,2,…,n直到迭代前后相同(或迭代次数m满足2m+1≥n)。

Floyd算法的核心部分可用 C语言表述为:

实际上,Floyd算法是用已知的顶点数较少的最短路径连接出顶点数较多的最短路径,枚举了所有可能的连接点,运算量很大,时间复杂度为 O (n3log2n)。 例 用 Floyd算法求图 1中各顶点间的最短路径长度。

解 用 Floyd算法求解过程如图 2、图 3所示,邻接矩阵如表1 中区域B12:F16、B19:F23所示。

相比图 1,图 2新增了 3条路径: v1v2v3,v2v3v4、v3v4v5

其中,路径 v1v2v3替换了图 1中较长路径 v1v3。 相比图 2,图 3新增了 3条路径: v1v2v3v4,v2v3v4v5,v1v2v3v4v5 它们相应替换了图 2中相应较长路径: v1v4,v2v5,v1v5

以下结合图 1给出 Floyd算法的三种演示。 2.1 演示 1

第 1步填写邻接矩阵。要点如下: (1)单元格 E3中填写公式 =E1＊E2。

上述单元格中也可填写其它足够大的数,使其大于任何两个顶点间的最短路径长度即可,相当于手工计算中的∞。

(2)单元格B5中填写公式 =＄E＄3,并设置条件格式,条件为“单元格数值”“等于”“=＄E＄3”,格式为“颜色”“白”,然后,把B5复制到区域B5:F9。 上述条件格式的目的是:对于不存在或尚未讨论到的路径,隐去其“长度”(前景与背景颜色相同)。

(3)如表1 所示,填写区域A1:F9中其它内容。 第 2步 填写迭代过程。要点如下:

(1)把区域A4:F9复制到A11:F14。 (2)单元格B12中填写数组公式

=M IN(＄B5:＄F5+TRANSPOSE(B＄5:B＄9))

并按组合键 Ctrl+Shift+Enter确认,然后,把 B12复制到区域B12:F16。 函数TRANSPOSE的调用格式为 TRANSPOSE(区域或数组) 用于返回给定矩阵的转置。

对于无向图,可省略上述公式中的转置函数。(3)单元格A12中填写数组公式 =AND(B5:F9=B12:F16)

并按组合键 Ctrl+Shift+Enter确认。

第 3步 重复迭代。复制区域 B12:F16,采用“选择性粘贴”把数值粘贴到区域 B5:F9,直到 A12中的检验值变为 TRUE为止。

经 2次重复迭代,最终结果如表2 所示(省略了与表1 相同的前半部分):

建议:完成第 2步后存盘,完成第 3步后,用“撤消”和“恢复”按钮重复演示迭代过程。 2.2 演示 2

第 1步 填写邻接矩阵。与演示 1相同。

第 2步 填写迭代过程。与演示 1基本相同,如表3 所示,G12:G16填写一组辅助数据,单元格B12中数组公式改为:

=M IN(＄B5:＄F5+TRANSPOSE(OFFSET(B5:B9, -＄G12,0))) 函数OFFSET的调用格式为 OFFSET(基准,行移,列移,行数,列数)

用于获取所需区域,其中,“基准”为单元格或区域,“行数”和“列数”可省略(与“基准”相同)。

第 3步 重复迭代。如表3 所示,复制区域A10:M16,重复向下粘贴,直到两次迭代间的检验值变为TRUE为止。

经 2次重复迭代,最终结果如表3 所示(省略了与表1 相同的前半部分): 相比演示 1,演示 2的公式略微复杂些,但保留了每次迭代的结果。 2.3 演示 3

在表3 的右侧添加表4 所示内容,用于显示相应路径(省略了起点和终点)。 第 1步 把表3 中区域A4:F9复制到区域 H4: M9、H11:M16、O11:T16,并相应修改文字。

第 2步 单元格 I5中填写公式 =″″,并复制到区域 I5:M9。 第 3步 单元格 P12中填写数组公式 =IF(B12＞=B5,″″,MATCH(B12+TRANSPOSE( OFFSET(B5:B9,-＄G12,0)),0))

并按组合键 Ctrl+Shift+Enter确认,然后,把 P12复制到区域 P12:T16。 函数MATCH的调用格式为 MATCH(数据,区域或数组,逻辑值)

用于返回指定数据在指定查找表中的序号,其中,“逻辑值”表示比较方式,FLASE或 0为精确比较。

第 4步 单元格 H12中填写数组公式=IF(B12＞=B5,″″,OFFSET(＄H5,0,P12) &OFFSET(＄A＄4,0,P12)&OFFSET(I4,P12-＄G12,0))并按组合键 Ctrl+Shift+Enter确认,然后,把H12复制到区域H12:M16。 第 5步 把区域 H11:T16复制到区域 H18: T24。

【相关文献】

[1] 胡运权主编.运筹学教程 (第二版)[M].北京:清华大学出版社,2003.

[2] Hamdy A.Taha.Operations Research An Introduction [M].北京:人民邮电出版社,2007. [3] 王成春,萧雅云主编.Excel2002函数应用秘芨[M].北京:中国铁道出版社,2002.