基于Floyd改進(jìn)加速算法的最短路徑選擇*

馬 瑩，陳志龍，劉 賀，趙銅星

(1.陸軍工程大學(xué) 國防工程學(xué)院，江蘇 南京 210007；2.海峽之聲廣播電臺(tái)，福建 福州 350000；3.解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，江蘇 南京 210007)

0 引言

最短路徑問題是求解復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的關(guān)鍵，是評(píng)價(jià)復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征，特別是大規(guī)模網(wǎng)絡(luò)的最短路徑問題一直是亟待解決的難題。如何對(duì)節(jié)點(diǎn)的重要性進(jìn)行有效評(píng)估并發(fā)現(xiàn)與實(shí)際情況相符的關(guān)鍵節(jié)點(diǎn)成為當(dāng)前研究的重點(diǎn)和熱點(diǎn)。張德全等人提出了不含負(fù)回路的網(wǎng)絡(luò)中 Floyd 加速算法及優(yōu)化方法，并構(gòu)造了求解最短路徑的序號(hào)矩陣[1]。王運(yùn)明等人針對(duì)目前指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法利用局部信息識(shí)別精度低、利用全局信息識(shí)別復(fù)雜度高的問題，提出了一種面向結(jié)構(gòu)洞的指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法[2]。嚴(yán)棟等人根據(jù)主觀與客觀賦權(quán)的特點(diǎn)，把熵權(quán)法的思想運(yùn)用到AHP 算法，建立了新的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法[3]。左秀峰等人針對(duì)最短路問題中存在多條等價(jià)最短路徑的問題，基于Floyd設(shè)計(jì)出新的搜索算法，在迭代更新距離矩陣與路徑矩陣的基礎(chǔ)上求出所有等價(jià)最短路徑[4]。HU P從節(jié)點(diǎn)的初始重要性以及相鄰節(jié)點(diǎn)和非相鄰節(jié)點(diǎn)之間的相互依賴強(qiáng)度所做的重要貢獻(xiàn)兩個(gè)角度提出了一種新的節(jié)點(diǎn)重要性評(píng)價(jià)方法，并將其應(yīng)用于電子郵件網(wǎng)絡(luò)[5]。周漩等人通過定義節(jié)點(diǎn)效率和節(jié)點(diǎn)重要度評(píng)價(jià)矩陣,提出了一種利用重要度評(píng)價(jià)矩陣來確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的方法[6]。曾瑛等人利用電網(wǎng)影響因子,并結(jié)合所定義的聚合系數(shù)指標(biāo),分析電力通信網(wǎng)中重要節(jié)點(diǎn)的分布密集狀況,得到各節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械南鄬?duì)重要性[7]。張喜平等人引入m階鄰居節(jié)點(diǎn)的概念,提出了一種基于m階鄰居節(jié)點(diǎn)重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度方法,并引入α和γ兩個(gè)參數(shù),用于調(diào)節(jié)節(jié)點(diǎn)重要度評(píng)估對(duì)節(jié)點(diǎn)自身特性及m階鄰居節(jié)點(diǎn)的依賴程度[8]。李鵬飛等針對(duì)傳統(tǒng)關(guān)鍵節(jié)點(diǎn)識(shí)別方法不能適應(yīng)Ad hoc網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性、計(jì)算復(fù)雜度高的問題,提出一種基于網(wǎng)絡(luò)連通性和節(jié)點(diǎn)刪除法相結(jié)合的關(guān)鍵節(jié)點(diǎn)識(shí)別方法[9]。

1 多層系統(tǒng)復(fù)雜網(wǎng)絡(luò)模型

就目前研究現(xiàn)狀來看，對(duì)多層系統(tǒng)復(fù)雜網(wǎng)絡(luò)的研究僅限于概念層面，在建模方式上采用單一類型的網(wǎng)絡(luò)，各子網(wǎng)要么均是隨機(jī)網(wǎng)絡(luò)，要么均是無標(biāo)度網(wǎng)絡(luò)，沒有區(qū)分子網(wǎng)的不同類型，而在實(shí)際網(wǎng)絡(luò)中，尤其是多層系統(tǒng)網(wǎng)絡(luò)，由于其復(fù)雜性而不可能存在單一的網(wǎng)絡(luò)連接方式。

針對(duì)這一問題，基于多層現(xiàn)實(shí)系統(tǒng)本體，區(qū)分出不同類型的網(wǎng)絡(luò)節(jié)點(diǎn)形式，并由核心層節(jié)點(diǎn)出發(fā)按各類網(wǎng)絡(luò)形式進(jìn)行輻射式構(gòu)建。在各子網(wǎng)間采用確定性連接與隨機(jī)性連接共存的混合連接方式構(gòu)建多層復(fù)雜系統(tǒng)網(wǎng)絡(luò)。

在確定性連接中存在“擇優(yōu)”與“扶貧”兩種連接方式，新的節(jié)點(diǎn)可能加到核心節(jié)點(diǎn)比較強(qiáng)的節(jié)點(diǎn)之下，使“強(qiáng)者更強(qiáng)”；也可能補(bǔ)充到功能較弱或者已經(jīng)被嚴(yán)重削弱的節(jié)點(diǎn)之下，彌補(bǔ)某個(gè)功能的不足。

在隨機(jī)性連接中又存在ER隨機(jī)網(wǎng)絡(luò)連接[10]和BA無標(biāo)度網(wǎng)絡(luò)連接兩種方式[11]，連接方法如下。

(1)ER隨機(jī)網(wǎng)絡(luò)連接：每次都從N1個(gè)核心網(wǎng)絡(luò)節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)與新加入的子網(wǎng)節(jié)點(diǎn)連接，直到所有的隨機(jī)連接節(jié)點(diǎn)全部連接到網(wǎng)絡(luò)中。

(2)BA無標(biāo)度網(wǎng)絡(luò)連接：新加入的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的核心網(wǎng)絡(luò)節(jié)點(diǎn)i以概率Pi連接:

(1)

從而，本文定義了反映網(wǎng)絡(luò)形式的三個(gè)比率：

其中t為總連接數(shù)；d為確定性連接數(shù)；r為隨機(jī)性連接數(shù)；s為確定性擇優(yōu)連接數(shù)；h為確定性扶貧連接數(shù)；b為BA無標(biāo)度網(wǎng)絡(luò)連接數(shù)；e為ER隨機(jī)網(wǎng)絡(luò)連接數(shù)；它們存在的關(guān)系為：t=d+r，d=s+h，r=b+e。

當(dāng)dt=br=0,sd無限制時(shí)，退化為ER隨機(jī)網(wǎng)絡(luò)連接；

當(dāng)dt=0,br=1,sd無限制時(shí)，退化為BA無標(biāo)度網(wǎng)絡(luò)連接；

當(dāng)dr=1,sd=1,br無限制時(shí)，為完全確定性擇優(yōu)連接；

當(dāng)dr=1,sd=0,br無限制時(shí)，為完全確定性扶貧連接。

用這三個(gè)比率可以靈活控制網(wǎng)絡(luò)的連接規(guī)律，從而生成不同的網(wǎng)絡(luò)模型。因此，混合連接多層網(wǎng)絡(luò)模型構(gòu)建方法如下：

步驟1 核心層節(jié)點(diǎn)標(biāo)號(hào), 確定3個(gè)混合比率(dtf,sdf,brf)；

步驟2 對(duì)每個(gè)新加入子網(wǎng)，生成m以內(nèi)的隨機(jī)數(shù)，代表該點(diǎn)的連邊數(shù)；

步驟3 生成d=Nn×dt個(gè)節(jié)點(diǎn)進(jìn)行確定性連接；

步驟4 按照核心節(jié)點(diǎn)的度值大小從大到小排序，將s=d×sd個(gè)新子網(wǎng)節(jié)點(diǎn)連接到前s個(gè)核心節(jié)點(diǎn)，將h=d×(1-sd)個(gè)新子網(wǎng)節(jié)點(diǎn)連接到后h個(gè)核心節(jié)點(diǎn)；

步驟5 生成r=Nn×(1-dt)個(gè)節(jié)點(diǎn)進(jìn)行隨機(jī)性連接；

步驟6 將b=r×brf個(gè)節(jié)點(diǎn)按照BA無標(biāo)度網(wǎng)絡(luò)規(guī)則連接到核心節(jié)點(diǎn)上；將g=r×(1-brf)個(gè)節(jié)點(diǎn)按照ER隨機(jī)網(wǎng)絡(luò)規(guī)則連接到核心節(jié)點(diǎn)上；

步驟7 新子網(wǎng)節(jié)點(diǎn)按概率Sh進(jìn)行ER隨機(jī)連接。

基于Netlogo仿真平臺(tái)構(gòu)建出的多層系統(tǒng)網(wǎng)絡(luò)模型有15個(gè)參數(shù)，具有很強(qiáng)的適用性，不同參數(shù)靈活組合可有成千上萬種變化，可以生成各種類型的目標(biāo)體系網(wǎng)絡(luò)模型。由于系統(tǒng)網(wǎng)絡(luò)模型的建模過程是基于核心層級(jí)輻射式建立的，因此該模型不僅能夠研究整個(gè)系統(tǒng)網(wǎng)絡(luò)的特征，也可以單獨(dú)研究其中某個(gè)子網(wǎng)絡(luò)的特征。

2 最短路徑算法研究

傳統(tǒng)的求解最短路徑的算法主要有Dijkstra算法和Floyd算法，其中Dijkstra算法是計(jì)算網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑的高效算法，而Floyd算法是計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間最短路徑的經(jīng)典算法。

因此，本文針對(duì)無向無權(quán)的復(fù)雜網(wǎng)絡(luò)，從這三點(diǎn)出發(fā)進(jìn)行優(yōu)化，提出了改進(jìn)的級(jí)聯(lián)失效算法，從而極大地提高計(jì)算效率。算法的優(yōu)化思路如下：

(1)無向無權(quán)網(wǎng)絡(luò)的距離矩陣D為對(duì)稱矩陣，所以有dij=dji，求得dij后直接賦值給dji即可，不需要再計(jì)算dji，即在算法的最內(nèi)層循環(huán)中，j不需要從1開始計(jì)算，而是從i+1開始計(jì)算，這樣j的平均計(jì)算次數(shù)減少為(n-1)/2，而且剔除了i=j的情況。

(2)當(dāng)k=i或k=j時(shí)，節(jié)點(diǎn)通過自身到達(dá)另一節(jié)點(diǎn)，長度沒有變化，不需要計(jì)算，i和j直接遞增。

(4)因?yàn)榫W(wǎng)絡(luò)直徑R在運(yùn)算結(jié)束前為未知數(shù)，所以設(shè)定一個(gè)變量C來表示還未找到最短路徑的節(jié)點(diǎn)對(duì)數(shù)量，當(dāng)dij改變時(shí)，變量C減2，當(dāng)C=0時(shí)，所有節(jié)點(diǎn)之間的最短路徑已經(jīng)找到，算法終止。

因此，假定網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)為n，關(guān)鍵節(jié)點(diǎn)評(píng)價(jià)算法的實(shí)現(xiàn)步驟如下：

令C為不相鄰的節(jié)點(diǎn)對(duì)總數(shù)。

步驟3：若C=0，則迭代結(jié)束；否則r=r+1，返回步驟2。

3 算法復(fù)雜性分析

改進(jìn)的Floyd加速算法共有四層循環(huán)，其中最外層r的循環(huán)次數(shù)為R-1，第二層k的循環(huán)次數(shù)為n，第三層i的平均循環(huán)次數(shù)為2L/n，其中L為邊數(shù)，第四層j的平均循環(huán)次數(shù)為(n-1)/2，算法總的復(fù)雜度為O((R-1)n(2L/n)(n-1)/2)=O((R-1)L(n-1))≈O(RLn)。通過分析可以看出，改進(jìn)的Floyd加速算法的計(jì)算復(fù)雜度與網(wǎng)絡(luò)直徑R和邊數(shù)L有關(guān)，當(dāng)R<

當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)n固定時(shí)，要使網(wǎng)絡(luò)連通，邊數(shù)L至少為n-1，此時(shí)網(wǎng)絡(luò)的直徑R=n-1， Floyd加速算法的計(jì)算復(fù)雜度為O((n-1)(n-1)n)≈O(n3)；當(dāng)網(wǎng)絡(luò)為完全連接網(wǎng)絡(luò)時(shí)L=n(n-1)/2，網(wǎng)絡(luò)直徑R=1，此時(shí)的計(jì)算復(fù)雜度為O(n2(n-1)/2)≈O(n3/2)。而該算法的最優(yōu)計(jì)算復(fù)雜度約為O(n2)，所以隨著網(wǎng)絡(luò)連接邊數(shù)的增加，該算法的計(jì)算復(fù)雜度先減小后增大。

4 算法優(yōu)越性驗(yàn)證

在Netlogo中生成節(jié)點(diǎn)數(shù)為10的某地域通信網(wǎng)干線節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)模型如圖1所示，下面計(jì)算所有節(jié)點(diǎn)間的最短路徑長度。

圖1 某地域通信網(wǎng)干線節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)圖

解：由圖1得到初始距離矩陣：

不相鄰的節(jié)點(diǎn)對(duì)數(shù)C=50

當(dāng)r=1，k=1時(shí)：

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；

當(dāng)r=1，k=2時(shí)：

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；

當(dāng)r=1，k=3時(shí)：

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時(shí)的距離矩陣：

當(dāng)r=2，k=1時(shí)：

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時(shí)的距離矩陣:

此時(shí)，所有節(jié)點(diǎn)對(duì)之間的最短距離都已經(jīng)找到，該網(wǎng)絡(luò)直徑為3，邊數(shù)為20，總的計(jì)算次數(shù)T=(3-1)×20×(10-1)=360，而經(jīng)典Floyd算法的計(jì)算次數(shù)為1 000，可以看出本文算法極大地降低了計(jì)算量。

文獻(xiàn)[12]中的Floyd加速算法的改進(jìn)方法是目前最新、適用性較廣且獲得結(jié)果較好的一種計(jì)算節(jié)點(diǎn)間最短路徑長度的方法，為驗(yàn)證本文算法的優(yōu)越性，分別用Floyd算法、文獻(xiàn)[12]改進(jìn)方法及本文算法求解隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的平均最短路徑長度來進(jìn)行對(duì)比驗(yàn)證，結(jié)果如表1～3所示。通過比較可以看出，針對(duì)最常用的三種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型，本文提出的改進(jìn)算法在計(jì)算節(jié)點(diǎn)間的最短路徑長度時(shí)，其計(jì)算復(fù)雜度較之經(jīng)典的Floyd算法和文獻(xiàn)[12]提出的改進(jìn)算法有明顯的降低，而且節(jié)點(diǎn)數(shù)量最大，優(yōu)勢越明顯。將本文提出的改進(jìn)的Floyd加速算法應(yīng)用到實(shí)際系統(tǒng)網(wǎng)絡(luò)評(píng)價(jià)之中，將會(huì)極大地提高算法的計(jì)算效率，從而提高算法的應(yīng)用價(jià)值。

5 結(jié)論

復(fù)雜網(wǎng)絡(luò)作為很多真實(shí)網(wǎng)絡(luò)的抽象，為描述和解決實(shí)際問題提供了一種途徑。針對(duì)多層系統(tǒng)網(wǎng)絡(luò)的研究，本文提出了一種新的輻射式建模方法并用新的改進(jìn)的Floyd加速算法評(píng)價(jià)了網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。本文所做的工作有以下幾點(diǎn)：首先，分析不同類型的節(jié)點(diǎn)連接方式，提出了混合類型連接方法。其次，以核心網(wǎng)為基礎(chǔ)，輻射式逐層生成系統(tǒng)網(wǎng)絡(luò)模型，提出了一種新的建模方式。最后，使用新提出的改進(jìn)的Floyd加速算法評(píng)價(jià)了網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。通過仿真結(jié)果與已有研究結(jié)果進(jìn)行對(duì)比，該方法不僅有很好的可靠性，還使得仿真時(shí)間縮短，達(dá)到了較好的仿真效果。 本文算法為多層網(wǎng)絡(luò)系統(tǒng)模型的建立和評(píng)估提出了一種新的思路，有著很好的理論價(jià)值和現(xiàn)實(shí)意義。

表1 隨機(jī)網(wǎng)絡(luò)模型三種算法復(fù)雜度對(duì)比

表2 小世界網(wǎng)絡(luò)模型(重連概率0.2)三種算法復(fù)雜度對(duì)比

表5 無標(biāo)度網(wǎng)絡(luò)模型三種算法復(fù)雜度對(duì)比

[1] 張德全,吳果林,劉登峰.最短路問題Floyd加速算法與優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(17):41-44.

[2] 王運(yùn)明,王青野,潘成勝,等.面向結(jié)構(gòu)洞的指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法[J].火力與指揮控制,2017,42(3):59-63.

[3] 嚴(yán)棟,張世斌,宗康,等.基于AHP-熵權(quán)法的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法[J].廣西大學(xué)學(xué)報(bào),2016,41(6):1933-1939.

[4] 左秀峰,沈萬杰.基于Floyd算法的多重最短路問題的改進(jìn)算法[J].計(jì)算機(jī)科學(xué),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] 周漩,張鳳鳴,李克武,等. 利用重要度評(píng)價(jià)矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)[J].物理學(xué)報(bào)，2012,61(5):1-7.

[7] 曾瑛,朱文紅,鄧博仁,等. 基于電網(wǎng)影響因子的電力通信網(wǎng)關(guān)鍵節(jié)點(diǎn)識(shí)別[J]. 電力系統(tǒng)保護(hù)與控制,2016,44(2):102-108.

[8] 張喜平,李永樹,劉剛,等. 節(jié)點(diǎn)重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2014,11(3):26-32

[9] 李鵬飛,雷迎科. 動(dòng)態(tài)Ad hoc網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別[J].計(jì)算機(jī)應(yīng)用研究，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ìn)算法[J].計(jì)算機(jī)科學(xué),2017,44(5):232-234,267.