改进Floyd算法在城市交通网络优化中的应用

（上海建桥学院 商学院，上海 201306）

1 引言

随着城市交通道路高速发展，交通网络间节点与路段日趋复杂，最短路径规划问题成为城市交通网络研究热点之一。最短路径规划不仅局限于路线设计及分析，还可引申到其它诸如时间、费用、线路容量等资源分配和优化问题[1-2]。在交通网络的规划设计中，大多数的优化模型都是以最短路径算法为基础，特别是在迭代的算法结构中，其最短路权矩阵计算子程序的调用频率较高[3-4]。因此，交通网络的最短路权矩阵算法的效率，可直接影响到局部规划设计模块乃至整个交通规划程序的运行速度。对Floyd算法进行改进，去除非必要中间节点路径计算，降低计算量，有效提高Floyd算法的计算效率，成为一个值得研究的课题[5]。

2 传统最短路径算法

建立交通网络最优线路问题数学模型的目的，是为寻找最优路径，为公众出行决策提供参考。目前，国际上采用较多的方法主要是Dijkstra算法。此算法可以找出网络中从某一节点到其余各点间的最短路径，其时间复杂度为O(n2)，其中n为网络节点的数目。而对于任意两点间的最短路径计算问题，最具有代表性的是Floyd算法。

2.1 Floyd算法思路

Floyd算法的迭代公式为：

式中的φ为运算号，其运算规则是：

反复迭代式（1），直至Ds=Ds-1，则最后的Ds就是最短路权矩阵。考察，如果前者小，表示路径不经过节点k，则其最短路径为，同时；如果后者小，则表示经过节点k,其最短路径为与两者的连接，设i,k两点最短路径，k,j两点最短路径其中，q,r≤s-1，u1,u2,...,uq,t1,t2,...,tr是节点集{v1,v2,...,vs-1}中q+r个不同节点的排列，则i,j两点最短路径，最短路长

2.2 Floyd算法复杂度

Floyd算法首先调用式（2），即任意i,j两点之间，需比较原路径与插入k节点后的路径长，其中k=1,2,...,n；然后再调用式（1），每次关于k的矩阵迭代还需要i,j取遍1,2,...,n，故整个算法的平均时间复杂度为O(n3)。对于算法的空间复杂度，需要两个n×n的矩阵，其中一个是最短路径序列的邻接矩阵，另一个是最短路长的权矩阵[6]。

3 改进的Floyd算法

传统的Floyd算法，是求解网络中任意两个节点间最短路的有效算法，但是关于最短路径的标记方法不尽相同，大部分算法使用一串数字作为下标来记录最短路径，标记的最短路径需逆向找寻。另外，Floyd算法在无向网络中运用时，在下标遍历时会出现大量重复的计算。为解决上述不足，本文基于传统的Floyd算法，提出了一种简便可行的无向网络上最短路径求解方法（有向图可视为无向图的特殊情形），并给出了避免重复计算的实例。

3.1 改进的算法思想

改进Floyd算法在计算最短路径过程中，采用双标号法，同时显示最短路径序列和最短路径长。同时，对最短路径长无影响的节点间路径值可以不予考虑，在整体上降低求解最短路径计算量，从而提高计算效率。

3.2 改进的算法步骤

步骤1 根据无向网络图得到距离矩阵。

D0=，其中i,j=1,2,...,n-1,n

（1）i=j时

（2）i与j不相连

（3）i与j相连时

采用双标号法建立初始表，行标用i，列标用j表示；每个单元格记，即对于初始表，每个单元格的双标号的前一位记最短路长，后一位记最短路径序列。为避免逆序出现，在节点i到节点j的路径上，tij表示节点i首先应到达的节点，在初始表中，，这就使得最终输出的tij（i,j=1,2,...,n-1,n）可顺序显示节点i到节点j的最短路径。

3.3 改进的算法复杂度

4 建模与分析

4.1 建模实例

为了模拟城市交通网络节点之间的最短路径规划，选取某城市核心区域的交通网络结构图作为初始的模型案例（如图1所示），模拟城市道路交通网络，构建无向网络赋权图（可假定道路可双向行驶，如图2所示）。运用改进的Floyd算法对任意两个节点之间的最短路径进行规划。

图1 城市交通网络图

图2 无向网络赋权图

4.2 模型假设

（1）本模型将城市道路交叉点视为网络节点，交叉口之间的路径抽象成为城市交通的网络边，保留了节点之间的关联关系，是城市道路交通网的拓扑结构图。

（2）图2所示的有向赋权图节点记为城市交通网络区域中选取的节点，未被选取的节点暂不纳入规划考虑范围之内。

（3）城市道路交通网络中的权值综合考虑了节点之间路径的实际长度、交通便捷程度及路况等信息，并结合谷歌地图的出行时间建议进行标注，在本文中视为两节点之间的路径长度。

4.3 算法求解

按改进的Floyd算法步骤，采用双标号法，建立初始表，见表1。

表1 k=1初始表

在表1基础上进行算法迭代，即插入节点②后，计算出最优路径，见表2。

表2 k=2最优路径表

在表2基础上进行算法迭代，即插入节点③后，计算出最优路径，见表3。

表3 k=3最优路径表

在表3基础上进行算法迭代，即插入节点④后，计算出最优路径，见表4。

表4 k=4最优路径表

在表4基础上进行算法迭代，即插入节点⑤后，计算出最优路径，见表5。

表5 k=5最优路径表

在表5基础上进行算法迭代，即插入节点⑥后，最优路径表（见表6）与表5时相同。此时对于j＜i且在上述迭代过程中最短路径有更改的单元格中，将原tij=j改为对称单元格相同的标号。

表6 k=6最优路径表

由此得出所有两节点间的最短路径序列与最短路径，见表7。

表7 最短路径序列与最短路径表

4.4 结果分析

对于本文的案例，用传统Floyd算法计算，需要进行216次。用文献[7]中的优化矩阵需要计算108次，改进Floyd算法采用判断语句将原计算量减少，只需进行五步迭代，60次计算。结果分析发现，在节点i到j之间最短路径规划过程中，改进的Floyd算法首先适当选择节点，然后再进入迭代计算，从而在很大程度上降低了算法所需运算次数、时间及空间复杂度，并有效完成城市道路交通节点间最短路径规划。

5 结语

最短路径算法在交通网络路径规划中有着广泛应用，除此之外，在设备更新、服务网点、配送中心选址及最小费用最大流等衍生的问题中也有着广泛的应用。本文提出的改进Floyd算法，采用先筛选再计算的模式，降低了冗余的计算并节省了存储空间，从而提高了算法的计算效率。以某市的交通网络为例，利用改进Floyd算法进行建模求解，计算结果表明：优化后的算法计算量明显减少，同时最短路径序列无需回溯找寻。在城市交通网络中实现最短路径规划，在理想模型假设条件之外，仍需要综合考虑众多元素[8]，为体现改进Floyd算法的可行性和实用性，本文路径权值并未探讨全部交通因素。接下来，可考虑带负权值或是带回路或是有向赋权网络等交通网络的最短路径规划问题，以体现改进Floyd算法处理多因素复杂交通网的有效性。