基于Floyd改进加速算法的最短路径选择*

马 莹，陈志龙，刘 贺，赵铜星

(1.陆军工程大学 国防工程学院，江苏 南京 210007；2.海峡之声广播电台，福建 福州 350000；3.解放军理工大学 野战工程学院，江苏 南京 210007)

0 引言

最短路径问题是求解复杂网络关键节点的关键，是评价复杂网络的一个重要特征，特别是大规模网络的最短路径问题一直是亟待解决的难题。如何对节点的重要性进行有效评估并发现与实际情况相符的关键节点成为当前研究的重点和热点。张德全等人提出了不含负回路的网络中 Floyd 加速算法及优化方法，并构造了求解最短路径的序号矩阵[1]。王运明等人针对目前指挥控制网络关键节点识别方法利用局部信息识别精度低、利用全局信息识别复杂度高的问题，提出了一种面向结构洞的指挥控制网络关键节点识别方法[2]。严栋等人根据主观与客观赋权的特点，把熵权法的思想运用到AHP 算法，建立了新的复杂网络关键节点识别方法[3]。左秀峰等人针对最短路问题中存在多条等价最短路径的问题，基于Floyd设计出新的搜索算法，在迭代更新距离矩阵与路径矩阵的基础上求出所有等价最短路径[4]。HU P从节点的初始重要性以及相邻节点和非相邻节点之间的相互依赖强度所做的重要贡献两个角度提出了一种新的节点重要性评价方法，并将其应用于电子邮件网络[5]。周漩等人通过定义节点效率和节点重要度评价矩阵,提出了一种利用重要度评价矩阵来确定复杂网络关键节点的方法[6]。曾瑛等人利用电网影响因子,并结合所定义的聚合系数指标,分析电力通信网中重要节点的分布密集状况,得到各节点在网络拓扑中的相对重要性[7]。张喜平等人引入m阶邻居节点的概念,提出了一种基于m阶邻居节点重要度贡献的复杂网络节点重要度方法,并引入α和γ两个参数,用于调节节点重要度评估对节点自身特性及m阶邻居节点的依赖程度[8]。李鹏飞等针对传统关键节点识别方法不能适应Ad hoc网络拓扑动态性、计算复杂度高的问题,提出一种基于网络连通性和节点删除法相结合的关键节点识别方法[9]。

1 多层系统复杂网络模型

就目前研究现状来看，对多层系统复杂网络的研究仅限于概念层面，在建模方式上采用单一类型的网络，各子网要么均是随机网络，要么均是无标度网络，没有区分子网的不同类型，而在实际网络中，尤其是多层系统网络，由于其复杂性而不可能存在单一的网络连接方式。

针对这一问题，基于多层现实系统本体，区分出不同类型的网络节点形式，并由核心层节点出发按各类网络形式进行辐射式构建。在各子网间采用确定性连接与随机性连接共存的混合连接方式构建多层复杂系统网络。

在确定性连接中存在“择优”与“扶贫”两种连接方式，新的节点可能加到核心节点比较强的节点之下，使“强者更强”；也可能补充到功能较弱或者已经被严重削弱的节点之下，弥补某个功能的不足。

在随机性连接中又存在ER随机网络连接[10]和BA无标度网络连接两种方式[11]，连接方法如下。

(1)ER随机网络连接：每次都从N1个核心网络节点中随机选择一个节点与新加入的子网节点连接，直到所有的随机连接节点全部连接到网络中。

(2)BA无标度网络连接：新加入的节点与一个已经存在的核心网络节点i以概率Pi连接:

(1)

从而，本文定义了反映网络形式的三个比率：

其中t为总连接数；d为确定性连接数；r为随机性连接数；s为确定性择优连接数；h为确定性扶贫连接数；b为BA无标度网络连接数；e为ER随机网络连接数；它们存在的关系为：t=d+r，d=s+h，r=b+e。

当dt=br=0,sd无限制时，退化为ER随机网络连接；

当dt=0,br=1,sd无限制时，退化为BA无标度网络连接；

当dr=1,sd=1,br无限制时，为完全确定性择优连接；

当dr=1,sd=0,br无限制时，为完全确定性扶贫连接。

用这三个比率可以灵活控制网络的连接规律，从而生成不同的网络模型。因此，混合连接多层网络模型构建方法如下：

步骤1 核心层节点标号, 确定3个混合比率(dtf,sdf,brf)；

步骤2 对每个新加入子网，生成m以内的随机数，代表该点的连边数；

步骤3 生成d=Nn×dt个节点进行确定性连接；

步骤4 按照核心节点的度值大小从大到小排序，将s=d×sd个新子网节点连接到前s个核心节点，将h=d×(1-sd)个新子网节点连接到后h个核心节点；

步骤5 生成r=Nn×(1-dt)个节点进行随机性连接；

步骤6 将b=r×brf个节点按照BA无标度网络规则连接到核心节点上；将g=r×(1-brf)个节点按照ER随机网络规则连接到核心节点上；

步骤7 新子网节点按概率Sh进行ER随机连接。

基于Netlogo仿真平台构建出的多层系统网络模型有15个参数，具有很强的适用性，不同参数灵活组合可有成千上万种变化，可以生成各种类型的目标体系网络模型。由于系统网络模型的建模过程是基于核心层级辐射式建立的，因此该模型不仅能够研究整个系统网络的特征，也可以单独研究其中某个子网络的特征。

2 最短路径算法研究

传统的求解最短路径的算法主要有Dijkstra算法和Floyd算法，其中Dijkstra算法是计算网络中一个节点到其他所有节点的最短路径的高效算法，而Floyd算法是计算网络中所有节点之间最短路径的经典算法。

因此，本文针对无向无权的复杂网络，从这三点出发进行优化，提出了改进的级联失效算法，从而极大地提高计算效率。算法的优化思路如下：

(1)无向无权网络的距离矩阵D为对称矩阵，所以有dij=dji，求得dij后直接赋值给dji即可，不需要再计算dji，即在算法的最内层循环中，j不需要从1开始计算，而是从i+1开始计算，这样j的平均计算次数减少为(n-1)/2，而且剔除了i=j的情况。

(2)当k=i或k=j时，节点通过自身到达另一节点，长度没有变化，不需要计算，i和j直接递增。

(4)因为网络直径R在运算结束前为未知数，所以设定一个变量C来表示还未找到最短路径的节点对数量，当dij改变时，变量C减2，当C=0时，所有节点之间的最短路径已经找到，算法终止。

因此，假定网络中的节点数为n，关键节点评价算法的实现步骤如下：

令C为不相邻的节点对总数。

步骤3：若C=0，则迭代结束；否则r=r+1，返回步骤2。

3 算法复杂性分析

改进的Floyd加速算法共有四层循环，其中最外层r的循环次数为R-1，第二层k的循环次数为n，第三层i的平均循环次数为2L/n，其中L为边数，第四层j的平均循环次数为(n-1)/2，算法总的复杂度为O((R-1)n(2L/n)(n-1)/2)=O((R-1)L(n-1))≈O(RLn)。通过分析可以看出，改进的Floyd加速算法的计算复杂度与网络直径R和边数L有关，当R<

当网络的节点数n固定时，要使网络连通，边数L至少为n-1，此时网络的直径R=n-1， Floyd加速算法的计算复杂度为O((n-1)(n-1)n)≈O(n3)；当网络为完全连接网络时L=n(n-1)/2，网络直径R=1，此时的计算复杂度为O(n2(n-1)/2)≈O(n3/2)。而该算法的最优计算复杂度约为O(n2)，所以随着网络连接边数的增加，该算法的计算复杂度先减小后增大。

4 算法优越性验证

在Netlogo中生成节点数为10的某地域通信网干线节点拓扑结构网络模型如图1所示，下面计算所有节点间的最短路径长度。

图1 某地域通信网干线节点拓扑结构网络图

解：由图1得到初始距离矩阵：

不相邻的节点对数C=50

当r=1，k=1时：

i=3，j=6，d36=1<2不变，j=7，d37=1<2不变，j=8，d38=>2，d38=d83=2；i=6，j=7，d67=>2，d67=d76=2，j=8，d68=>2，d68=d86=2；i=7，j=8，d78=>2，d78=d87=2；

当r=1，k=2时：

i=4，j=6，d46=>2 ，d46=d64=2，j=8，d48=1<2不变，j=9，d49=>2，d49=d94=2；i=6，j=8，d68=2不变，j=9，d69=>2，d69=d96=2；i=8，j=9，d89=>2，d89=d98=2；

当r=1，k=3时：

i=1，j=4，d14=>2 ，d14=d41=2，j=5，d15=>2，d14=d41=2，j=6，d16=1<2不变，j=7，d17=1<2不变，j=9，d19=>2，d19=d91=2；i=4，j=6，d46=2不变，j=7，d47=>2，d47=d74=2，j=9，d49=>2，d49=d94=2；i=5，j=6，d56=>2，d56=d65=2，j=7，d57=1<2不变，j=9，d59=>2，d59=d95=2；i=6，j=9，d69=>2，d69=d96=2；i=7，j=9，d79=1<2不变； ……

得到r=1时的距离矩阵：

当r=2，k=1时：

i=3，j=4，d34=1<3不变，j=5，d35=1<3不变，j=9，d39=1<3不变，j=10，d3,10=2<3不变；i=6，j=9，d69=2<3不变，j=10，d6,10=1<3不变；i=7，j=9，d19=1<3不变，j=10，d7,10=>3，d7,10=d10,7=3；……

得到r=2时的距离矩阵:

此时，所有节点对之间的最短距离都已经找到，该网络直径为3，边数为20，总的计算次数T=(3-1)×20×(10-1)=360，而经典Floyd算法的计算次数为1 000，可以看出本文算法极大地降低了计算量。

文献[12]中的Floyd加速算法的改进方法是目前最新、适用性较广且获得结果较好的一种计算节点间最短路径长度的方法，为验证本文算法的优越性，分别用Floyd算法、文献[12]改进方法及本文算法求解随机网络、小世界网络和无标度网络的平均最短路径长度来进行对比验证，结果如表1～3所示。通过比较可以看出，针对最常用的三种网络拓扑结构模型，本文提出的改进算法在计算节点间的最短路径长度时，其计算复杂度较之经典的Floyd算法和文献[12]提出的改进算法有明显的降低，而且节点数量最大，优势越明显。将本文提出的改进的Floyd加速算法应用到实际系统网络评价之中，将会极大地提高算法的计算效率，从而提高算法的应用价值。

5 结论

复杂网络作为很多真实网络的抽象，为描述和解决实际问题提供了一种途径。针对多层系统网络的研究，本文提出了一种新的辐射式建模方法并用新的改进的Floyd加速算法评价了网络节点的重要性。本文所做的工作有以下几点：首先，分析不同类型的节点连接方式，提出了混合类型连接方法。其次，以核心网为基础，辐射式逐层生成系统网络模型，提出了一种新的建模方式。最后，使用新提出的改进的Floyd加速算法评价了网络中节点的重要性。通过仿真结果与已有研究结果进行对比，该方法不仅有很好的可靠性，还使得仿真时间缩短，达到了较好的仿真效果。 本文算法为多层网络系统模型的建立和评估提出了一种新的思路，有着很好的理论价值和现实意义。

表1 随机网络模型三种算法复杂度对比

表2 小世界网络模型(重连概率0.2)三种算法复杂度对比

表5 无标度网络模型三种算法复杂度对比

[1] 张德全,吴果林,刘登峰.最短路问题Floyd加速算法与优化[J].计算机工程与应用,2009,45(17):41-44.

[2] 王运明,王青野,潘成胜,等.面向结构洞的指挥控制网络关键节点识别方法[J].火力与指挥控制,2017,42(3):59-63.

[3] 严栋,张世斌,宗康,等.基于AHP-熵权法的复杂网络关键节点识别方法[J].广西大学学报,2016,41(6):1933-1939.

[4] 左秀峰,沈万杰.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,2017,44(5):232-234,267.

[5] HU P, FAN W, MEI S. Identifying node importance in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2015, 429: 169-176.

[6] 周漩,张凤鸣,李克武,等. 利用重要度评价矩阵确定复杂网络关键节点[J].物理学报，2012,61(5):1-7.

[7] 曾瑛,朱文红,邓博仁,等. 基于电网影响因子的电力通信网关键节点识别[J]. 电力系统保护与控制,2016,44(2):102-108.

[8] 张喜平,李永树,刘刚,等. 节点重要度贡献的复杂网络节点重要度评估方法[J]. 复杂系统与复杂性科学,2014,11(3):26-32

[9] 李鹏飞,雷迎科. 动态Ad hoc网络关键节点识别[J].计算机应用研究，2017,34(5)：1473-1475.

[10] INSOO S. Small-world and scale-free network models for IoT systems[J]. Mobile Information Systems, 2017(61): 1-9.

[12] 左秀峰,沈万杰.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,2017,44(5):232-234,267.