一種快速求解最短路徑巡游問題的漣漪擴散算法

摘 要：針對最短路徑巡游問題（SPTP），提出了基于漣漪擴散算法（RSA）特征的SPTP分解方法。RSA通過模擬水面上漣漪傳播的現象，在SPTP子問題間建立聯系，相較于其他基于問題分解的算法減少了計算冗余度。進一步改進RSA，使其在維持時間復雜度不變的情況下求解多起點—多終點SPTP。在多種拓撲結構的網絡中進行對比實驗，結果表明，RSA在保證最優性的同時運算效率最高。RSA對于多起點—多終點SPTP的高效求解，可為多種現實問題快速提供解決方案，具有很高的應用價值。

關鍵詞：最短路徑巡游問題；漣漪擴散算法；問題分解；路徑優化；多對多路徑優化

中圖分類號：TP301 文獻標志碼：A 文章編號：1001-3695（2022）11-015-3298-05

doi： 10.19734/j.issn.1001-3695.2022.03.0150

Efficient ripple-spreading algorithm for the shortest path tour problem

Ma Yiminga， Hu Xiaobingb， Zhou Hanga

（a.Sino-European Institute of Aviation Engineering， b.College of Safety Science amp; Engineering， Civil Aviation University of China， Tianjin 300300， China）

Abstract：For the shortest path tour problem （SPTP）， this paper proposed the specific decomposition method for the ripple-spreading algorithm （RSA） to solve the SPTP. The RSA simulated ripple propagation patterns on the water surface and established connections among subproblems， which reduced computational redundancy compared to other decomposition methods. This paper adapted the RSA to make it solve the SPTP with multiple sources and destinations while maintaining time complexity. Comparative experiments on various network topologies show that the RSA ensures optimality and outperforms other algorithms in computational efficiency. The efficiency of the RSA when solving the SPTP with multiple sources and destinations makes it can provide solutions to real-world problems efficiently and demonstrates its application values.

Key words：SPTP; ripple-spreading algorithm; decomposition method; path optimization; many-to-many path optimization

基金項目：天津市教委科研計劃資助項目（2020KJ037）

作者簡介：馬一鳴（1997-），男，河北石家莊人，碩士研究生，主要研究方向為計算智能；胡小兵（1975-），男（通信作者），四川攀枝花人，教授，博導，博士，主要研究方向為計算智能、復雜系統和綜合風險管理（huxbtg@163.com）；周航（1990-），男，天津人，講師，博士，主要研究方向為計算智能、計算電磁學和無人機開發.

最短路徑問題（shortest path problem，SPP）是圖論與計算機科學領域的一類經典問題，許多劃時代的算法成功地解決了該問題，并在現實中得到了廣泛應用［1～3］。最短路徑巡游問題（SPTP）是SPP的一個擴展問題，于20世紀70年代被Bajaj［4］提出，其目的是尋找一條兩節點之間的最短路徑，且該路徑必須按照順序通過K個互不相交的節點子集。SPTP具有廣泛的應用場景，例如機器人控制、倉庫管理等［5］。隨著5G技術的發展，網絡功能虛擬化（network functions virtualization，NFV）成為當下熱門網絡技術之一［6～8］。NFV的難點之一是如何高效部署虛擬網絡資源，即在成本盡量小的情況下尋找一系列完成虛擬功能的節點［9， 10］。已有文獻證明，該問題與SPTP具有高度相似性，并且NFV網絡一般可抽象為層狀網絡的結構［11～13］。

目前SPTP的求解算法主要分為網絡改造法、問題分解法、動態規劃法、深度優先搜索和整數線性規劃法幾類。2012年，Festa［14］利用網絡改造法證明了SPTP是屬于多項式時間復雜度的，隨后他又提出網絡改造法modified graph algorithm （MGA）［15］，該類方法在大規模網絡中會花費大量的算力進行網絡改造，從而降低效率；文獻［11］提出了利用問題分解法求解SPTP算法的基本框架，即第m個子問題將第m個節點子集作為起點集合，將第m+1個節點子集作為終點集合，并對比了許多求解SPTP子問題的算法，證明DC-SSSP-2的表現優于其他算法。然而目前該類算法每個子問題需要計算每對起點與終點之間的最短路徑，造成了過高的計算冗余度。Bertsekas［16］提出可用動態規劃求解SPTP；Festa等人［15］隨后提出求解SPTP的dynamic programming algorithm （DPA），該方法在不同拓撲結構的網絡中運算效率差別較大；Bhat等人［11］提出的基于深度優先搜索的算法depth first tour search （DFTS）表現出較好的效率；Sasabe等人［9］于2020年將SPTP建模為整數線性規劃模型，并利用優化求解軟件CPLEX對SPTP進行求解。

本文提出基于漣漪擴散算法（ripple-spreading algorithm， RSA）特征的SPTP分解方法，并改進RSA對SPTP子問題進行求解。該算法可減少傳統基于問題分解的SPTP算法的計算冗余度，提高SPTP求解效率；并在維持時間復雜度不變的情況下，利用RSA求解多起點—多終點SPTP。

1 問題模型

現給定一個有向連通圖G={N，E}，其中N={n1，…，nn}為節點集合，E={（i，j）|i∈N，j∈N}為邊集合。圖中節點的個數為nn，邊的個數為ne，起點為s，終點為d。每條邊（i，j）具有一個大于0的權wij。假設存在K個互不相交的節點子集S1，S2，…，SK，即對于i，j=1，…，K，i≠j，滿足Si∩Sj=。為了描述方便，定義S1={s}，SK=g0gggggg。定義節點i的前序節點集合F（i）={j|（i，j）∈E}和后序節點集合B（i）={j|（j，i）∈E}。SPTP的目的是尋找一條從s到d的最短路徑，且該最短路徑按順序經過K個節點子集中的至少一個節點，可描述為

2 算法設計

RSA的提出受到了如下自然現象的啟發：水面上的漣漪向各個方向以相同速度擴散，當漣漪觸碰到障礙物（如石頭）時，會觸發新的漣漪繼續向前擴散，這樣就在水面上形成了漣漪接力賽。其中蘊涵了一個重要的優化思想：一個節點被不同漣漪訪問的順序，與漣漪經過的路徑長度順序相同，即第一個到達某節點的漣漪必定走過最短的路徑［17］。

2.1 基于RSA特征的SPTP分解方法

文獻［11］中提出了基于問題分解的SPTP求解算法的基本框架，并將SPTP分解為K－1個子問題。該框架下每個子問題需要計算每對起點與終點之間的最短路徑，并且各子問題之間相互獨立?，F給出基于RSA特征的SPTP分解方法，可在減少計算冗余度的同時，在子問題之間建立聯系。

算法1 基于RSA特征的SPTP分解方法

輸入：有向連通圖G={N，E}，節點子集S1，S2，…，SK。

輸出：SPTP最短路徑。

a） 初始化Tinit={0}，Rinit={0}，P={};

b） for m=1，…，K－1

c） S=Sm; // 起點集合為Sm

d） D=Sm+1; // 終點集合為Sm+1

e） Pd，Tinit，Rinit=RSA（S，D，Tinit，Rinit，G）; // 利用RSA求解

f） P=P∪Pd; // 將結果記錄到P集合中

g） end for

h） 從集合P回溯得到SPTP最短路徑;

由算法1可知，第m個子問題可被建模如下：起點集合為Sm，終點集合為Sm+1，起始時間集合為Tinit，起始半徑集合為Rinit。在每一次循環中，Tinit和Rinit會根據RSA對SPTP子問題的求解進行更新。即利用基于RSA特征的SPTP分解方法，各子問題之間不相互獨立，一個子問題的初始條件取決于上一個子問題的輸出。

假設節點子集Sm包含nm個節點，利用圖2（a）中SPTP的一般分解方法需要計算最短路的數目為n21×n22×…×n2K；圖2（b）中基于RSA特征的SPTP分解方法需要計算最短路的數目為n2+n3+…+nK。對比其他分解算法，RSA可大幅度減少計算冗余度并提升算法效率。

2.2 改進RSA求解SPTP子問題

本節將提出如何改進RSA求解SPTP子問題。對于第m個子問題：起點集合為Sm，終點集合為Sm+1，起始時間集合為Tinit，起始半徑集合為Rinit。對于Sm中的第i個節點，在時間Tinit（i）時會初始化一個半徑為Rinit（i）的漣漪。由于SPTP只關注最短路徑，不失最優性，每個節點只能產生一個漣漪［17］，并定義在節點i處產生的漣漪為漣漪i。表1列出了RSA中使用的符號說明，算法2提供了RSA求解SPTP子問題的偽代碼，圖3利用流程圖的形式解釋了RSA的執行過程。

算法2 利用RSA求解SPTP子問題

輸入：S，D，Tinit，Rinit，G={N，E}。

輸出：Pd，Td，Rd。

1 R（i）=T（i）=0，i=1，…，nn，ΩAR={}，ΩIAR={1，…，nn};

2 Pd，Td，Rd={}，t=min（Tinit）－1;

3 v=min（wij）; // 選取漣漪擴散速度

4 while i∈D，T（i）=0 // 終止條件判斷

5 t=t+1; // 時間增加一個單位

6 i∈ΩAR，r（i）=r（i）+v; //處于激活狀態的漣漪進行擴散

7 for i=1，…，nS

8 if S（i）∈ΩIAR amp;amp; t=Tinit（i）

9 r（S（i））=Rinit（i），T（S（i））=－1; //初始化漣漪

10 end if

11 end for

12 for i∈ΩAR

13 for j∈F（i）

14 if j∈ΩIAR amp;amp; R（i）≥R（j）+wij

15 R（j）=R（i）－wij，T（j）=i； //觸發漣漪

16 end if

17 end for

18 if j∈F（i），R（i）≥wij

19 ΩAR=ΩAR－{i}; // 漣漪狀態更新

20 end if

21 for i updated in line 9 and 15

22 ΩIAR=ΩIAR－{i}，ΩAR=ΩAR+{i};

23 if i∈D

24 Td=Td+{t}，Rd=Rd+{R（i）}; // 記錄輸出

25 end if

26 end for

27 end while

28 根據T回溯到達每個D中節點的漣漪經過的路徑。

2.3 求解多起點—多終點SPTP

NFV網絡更多地被建模為多起點—多終點SPTP，其目的是為每個起點尋找一條到達任意終點的最短路徑［18］。將SPTP算法拓展到多起點—多終點情況上，最直接的方式是選取不同的起點和終點重復執行多次算法，確定每一對起點與終點間滿足SPTP約束的最短路徑，這種做法會增加算法的時間復雜度。

從算法設計的角度考慮，存在將RSA拓展到多起點—多終點SPTP并且只需執行一次的方式：反轉網絡，即改變所有邊的方向，并反轉K個節點子集的順序SK，…，S1。假設S1包含n1個節點，SK包含nK個節點，則算法1中的初始化步驟改變為Tinit=Rinit={0，…，0}，P={}，其中Tinit和Rinit中包含元素的個數為nK。執行一次算法，可以得到從SK中節點到達S1中每個節點的n1條最短路徑，反轉即可確定多起點—多終點SPTP的最優解。

算法3 利用RSA求解多起點—多終點SPTP

輸入：有向連通圖G={N，E}，節點子集S1，S2，…，SK。

輸出：SPTP最短路徑。

a） 初始化P={};

b） 初始化Tinit=Rinit={0，…，0}; // 0的個數為nK

c） G′={N，E′}，E′={（j，i）∣（i，j）∈E}; // 反轉網絡

d） for （i，j）∈E

e） w′ji=wij; // 定義網絡G′每條邊（j，i）的權重w′ji

f） end for

g） for m=K，K－1，…，2

h） S=Sm; // 起點集合為Sm

i） D=Sm－1; // 終點集合為Sm－1

j） Pd，Tinit，Rinit=RSA（S，D，Tinit，Rinit，G′）; //利用RSA求解

k） P=P∪Pd; // 將結果記錄到P集合中

l） end for

m）從集合P回溯得到SPTP最短路徑，并反轉路徑。

2.4 算法實例

圖4提供了一個利用RSA求解SPTP的實例，只展示處于激活狀態的漣漪，并且在節點i處產生的漣漪命名為Ri。節點子集為S1={1}，S2={2，4}，S3={5，6}，S4={7}。圖4中，圖（a）t=0，第一個子問題，漣漪R1，在節點1處完成初始化，r=0；（b）t=1，第一個子問題，漣漪R1向前擴散，并在節點2處觸發半徑為0的漣漪R2；圖（c）t=2，第一個子問題，R1到達節點3和4，并且觸發兩個半徑為1的漣漪R3和R4，所有S2中的節點被訪問，該子問題結束；圖（d）t=2，第二個子問題，漣漪R3和R4根據第一個子問題的輸出初始化，并且R2轉換為終止狀態；圖（e）t=3，第二個子問題，漣漪R4到達節點5和6，觸發漣漪的半徑分別為1和0，S3內所有節點被訪問，第二個子問題結束；圖（f）t=4，第三個子問題，R5到達節點7，半徑為1，整個算法結束，SPTP最優解為：1→4→5→7，成本為t×v-r=7。

圖4（c）是第一個子問題的最后一步，圖4（d）是第二個子問題的第一步。在第二個子問題中，位于S2中節點處的漣漪被保留，其余的漣漪不包含SPTP最短路徑的信息，被清除以減少計算冗余度。

3 算法分析

3.1 最優性分析

在第m個子問題中，假設終點集合Sm+1包含nm+1個節點，終止條件為Sm+1中的節點均被漣漪訪問。在子問題結束后，會得到nm+1條到達每個終點的路徑，定義集合Pm包含這些路徑。

定理1 SPTP的最短路徑由每個子問題得到的路徑集合Pm中的路徑構成，m=1，…，K－1。

證明 利用反證法來進行證明。假設最短路徑Po中包含不屬于路徑集合Pm中的路徑，m=1，…，K－1。不失一般性，假設Po只包含一段路徑pm不屬于Pm。定義節點n是路徑pm的終點。由于pmPm，經過路徑pm的漣漪不是第一個到達節點n的漣漪。假設第一個到達n的漣漪R1在時間t1到達，觸發漣漪的半徑為r1；漣漪R2通過路徑pm于時間t2到達n，觸發的漣漪半徑為r2。根據算法2第14行，可以得到（t1lt;t2）或（t1=t2，r1gt;r2）。則R1從起點s到節點n經過的路徑總長度為（t1×v－r1），R2為（t2×v－r2）。由于（t1×s－r1）lt;（t2×s－r2），所以路徑Po不是SPTP的最短路徑，假設不成立，定理1得證。

定理2 在最后一個子問題中首先到達終點d的漣漪必定經過SPTP的最短路徑。

證明 由于SPTP被分解為K－1個子問題，最后一個子問題中的路徑必定按照順序經過節點子集S1，…，SK－1，即所有到達終點d的漣漪經過的路徑必定是符合SPTP約束的。根據RSA優化思想，第一個到達節點的漣漪必定經過最短的路徑［17］。漣漪擴散的過程在不同子問題之間具有連續性，所以第一個到達d的漣漪必定經過SPTP的最短路徑，定理2得證。

定理1和2說明RSA可保證求解SPTP的最優性，并且各個子問題間不是獨立的。將SPTP分解的目的是清理無用的（不攜帶全局最優解信息的）漣漪，減少計算冗余度。

3.2 時間復雜度

在RSA中，最基本的運算步驟包括漣漪在邊上擴散，并將當前漣漪半徑與邊的權進行比較。網絡G擁有nn個節點和ne條邊，所以每個節點平均擁有ne/nn條邊。假設每個漣漪平均花費natu個模擬時間單位通過一條邊。在每個子問題中，假設起點集合擁有ns個起點，終點集合擁有nd個終點，并且每個節點至多可觸發一個漣漪。則在最壞的情況下，每個起點需要natu×ne/nn個運算步驟；終點不需要運算步驟；其余的（nn－ns－nd）個中間節點需要natu×（ne/nn－1）個運算步驟，因為至少一個與其相連的節點已被漣漪訪問。在最壞的情況下，一個子問題需要nbcs個運算步驟：

在大規模網絡中，起點遠少于中間節點，即nslt;lt;nn。從而RSA求解一個子問題的時間復雜度為O（natu×ne）。子問題的數目為K－1，從而RSA的時間復雜度為O（K×natu×ne）。

對于多起點—多終點SPTP，唯一的區別是S1和SK中節點的數目大于1。由于起點數目遠小于中間節點數目仍然成立，從而RSA求解多起點—多終點SPTP的時間復雜度同樣為O（K×natu×ne）。

表2列出了不同SPTP算法的時間復雜度，可看出RSA是唯一時間復雜度與節點數目nn無關的算法。在邊的數目固定的大規模稀疏網絡中，RSA在理論上具有更高的效率。與表2中其他算法相比，RSA是唯一的受自然啟發的、基于自組織個體的算法，具有更高的可擴展性［17］。例如，如圖3所示，RSA求解SPTP時每個節點至多觸發一個漣漪。通過增加每個節點可產生漣漪的數目，RSA可求解SPTP的前k條最短路徑問題。

4 實驗

本章將進行RSA與其他SPTP算法的效率對比，并且探討特定參數對RSA運算效率的影響，之后對比RSA求解SPTP與多起點—多終點SPTP的運行時間，以證明RSA求解兩問題的時間復雜度相同，并通過一個實際案例證明RSA的應用價值。本章中所有實驗的運行時間均為執行50次隨機實驗的平均時間。實驗環境：Intel Core i7-10850H CPU 2.70 GHz，32 GB內存，Windows 10操作系統，所有算法均用Python 3.9編程實現。

4.1 綜合對比實驗

本節將在多種拓撲結構的網絡中進行測試。假設每個節點子集平均擁有ns個節點，每個節點平均擁有na條邊。選取文獻［14，15］中的EGA、MGA和DPA以及文獻［11］中的DC-SSSP-2與本文提出的RSA進行對比實驗。五種算法在相同的網絡中運行，由于得到的SPTP最短路徑相同，在此只關注運算效率。

a）完全隨機網絡。這種網絡根據文獻［19］中的ER網絡理論生成，每個節點以概率p與其他所有節點直接相連。

b）網格狀網絡。該矩形網絡擁有nr行和nc列，每個節點只與其周圍的節點相連，路徑長度定義為實際的空間距離。

c）公路網絡。該網絡用來模擬城市中的公路網絡。引入非直線系數η的概念，其代表真實路徑長度與空間直線距離的比值。網格狀網絡中每條路徑的長度乘以η，并且每條路徑有（1－p）的概率被清除，就可得到公路網絡。

d）層狀網絡。該網絡用來模擬NFV的網絡結構，每個節點都屬于一個節點子集，即|S1|+…+|SK|=nn，并且第m個集合中的節點只能與第m－1和第m+1個集合中的節點相連。

首先在完全隨機網絡中進行對比實驗，ne的值從［250，500，1 000，2 000，3 500，5 000］中選取；K取值為5或10；ns選取固定值25；關于網絡中邊密度的參數p取值為0.1或0.2。

從圖5中的結果中可以看出，RSA是五種算法中最高效的。無論節點子集數目（K）、節點數目（nn）和邊密度（p）的取值，RSA都表現出了運算效率上的很大優勢。選取運算效率最高的三種算法：RSA、DPA和DC-SSSP-2，計算在完全隨機網絡測試中的運行總時間，分別為208.52 s、1 082.72 s和852.68 s，可看出RSA的運算效率相較于其他算法至少提升了4倍。

在網格狀網絡與公路網絡的測試中，nr和nc在10～25取值。在網格狀網絡中，每條邊的權取值為1；在公路網絡中，非直線系數η在［1.1，1.4］均勻分布，p取定值0.9。在這兩種網絡中，設置K=5，ns=15。對比結果展示在圖6中，可看出RSA是在網格狀網絡和公路網絡中最具有效率的算法。

利用兩個實驗對比不同算法在層狀網絡中的效率。首先，保持網絡層數為5，節點數量從100增加到1 000，結果如圖7（a）所示；其次，保持節點數目為250，網絡層數從5增加到25，結果如圖7（b）所示。從實驗結果來看，RSA在層狀網絡中運算效率最高，展現了RSA應用在NFV網絡中的潛力。

4.2 特定參數影響

在本節將分析某些特定參數對RSA運算效率的影響。首先，保持nn=1 000，K=15，ne=5 000不變，節點子集中的平均節點數目ns從2增加到50；其次，研究K對運算效率的影響，保持nn=2 000，ns=50，ne=10 000不變，K從3增加到30；最后，研究網絡中邊的密度對運算效率的影響，保持nn=1 000，K=10，ns=50不變，每個節點上邊的數目na從5增加到100。以上實驗選擇DC-SSSP-2做參照，結果如圖8所示。

如圖8（a）所示，DC-SSSP-2的運行時間大致與ns保持線性關系，而RSA的運行時間幾乎不隨ns的增加而改變。在一開始，DC-SSSP-2的運算效率高于RSA，當ns到達22時，RSA的運算效率反超DC-SSSP-2；在圖8（b）中，兩算法的運行時間都隨K的增加線性增長，然而RSA的運行時間增長速度較慢；在圖8（c）中，RSA的運算效率遠超DC-SSSP-2，當每個節點平均擁有100條邊時，RSA的運算效率比DC-SSSP-2高出10倍。從這些實驗可看出，RSA的運算效率幾乎不隨邊的數目或每個節點子集平均擁有節點的數目改變，并且在節點子集數目增加時，RSA運行時間增加更為緩慢。

由3.2節分析，RSA的時間復雜度與漣漪通過一條邊平均花費的模擬時間單位natu相關。由算法2可知，漣漪按照速度v=min（wij）擴散，所以natu取決于最大權與最小權的比值，并將該比值記為β。在參數為nn=500，ne=2 000，K=5，ns=50的完全隨機網絡中研究β對RSA運算效率的影響，β在2～100取值。本實驗選擇DPA和DC-SSSP-2作為參照，并記錄RSA運算過程中產生的漣漪數目、natu和進行的計算步驟數目。

實驗結果如表3所示，其中運行時間以ms為單位。β的取值從2～100增加了50倍，但natu僅增加了15倍，并且產生的漣漪數目不斷減少。不僅如此，在β=80時，RSA運算效率仍最高。該實驗表明了RSA的運算效率面對β的改變具有較高的穩健性。在實際應用中，如果網絡中某條邊的權相對于邊的平均權過小，可將這條邊的兩節點融合為一個節點，在網絡改變不大的情況下進一步提高RSA的運算效率。

4.3 多起點—多終點SPTP

本節將在完全隨機網絡中進行實驗，證明RSA在求解多起點—多終點SPTP時可保持時間復雜度不變。通過在SPTP中加入起點和終點，生成多起點—多終點SPTP。定義起點和終點的數目為nm，nm取值為［1，5，10，20］。在此實驗中，節點個數nn從200增加到5 000，間隔為200，節點子集數目從10增加到30。

結果如表4所示，RSA在求解SPTP（nm=1）與多起點—多終點SPTP（nmgt;1）時運行時間大致相同，通過實驗的方法證明了RSA求解兩問題時具有相同的時間復雜度。由于沒有其他算法在多起點—多終點SPTP上的研究，可以粗略地認為其他算法需要計算每對起點與終點間的SPTP最短路徑，所以需要執行n2m次。而RSA只需執行一次就可解決多起點—多終點SPTP，相較于其他算法具有明顯優勢。

4.4 實際案例分析

本節引入一個同城快遞的實際案例以證明RSA的實際應用價值。在多分配快遞模式中，一個分撥中心可以與多個樞紐相連，并且兩分撥中心之間的快遞運輸只能通過樞紐中轉［20］。選擇河南省鄭州市的中心路網進行測試，該網絡包含550個節點和1 910條邊，如圖9所示。分撥中心1包含兩個起點，分撥中心2包含三個終點?？爝f從分撥中心1集中到樞紐1中的某個樞紐，并發往樞紐2中的某個樞紐，之后分配到分撥中心2。本案例目的是尋找每對起點與終點之間的最短快遞運輸路徑，該問題可建模為SPTP，其中四個節點子集分別為分撥中心1、樞紐1、2和分撥中心2。

對比結果如表5所示，其中運行時間以ms為單位。由于RSA僅需一次計算，就可求得從一個起點到達所有終點的SPTP最短路徑，所以RSA求解實際案例的總運行時間為171 ms，而對比算法中運算效率最高的DC-SSSP-2的總運行時間為871 ms。利用RSA求解該實際案例，運行效率提升5倍，并且在終點數目增多的情況下，RSA的運行效率相較于其他算法的優勢會更加明顯。通過此實際案例分析，證明了RSA在真實路網環境中具有很高的應用價值。

5 結束語

本文利用受到水面漣漪傳播現象啟發而提出的漣漪擴散算法（RSA）求解最短路徑巡游問題（SPTP）。首先提出基于RSA特征的SPTP分解方法，將擁有K個節點子集的SPTP分解為K－1個子問題。然后改進RSA求解SPTP子問題，最后將RSA擴展到解決多起點—多終點SPTP。通過算法最優性理論證明、時間復雜度分析和對比實驗，可總結出RSA在解決SPTP時具有以下優點：a）RSA在子問題之間建立了聯系，通過避免求解每對起點與終點之間的最短路來降低運算冗余度；b）只需執行一次算法就可解決一個SPTP子問題；c）經過分析，在網絡中邊的數目固定時，RSA的時間復雜度與節點數目無關，在大規模稀疏網絡中具有更高的效率；d）RSA求解多起點—多終點SPTP可維持時間復雜度不變；e）在實驗中，RSA在各種網絡中的表現均優于其他算法。

未來工作可以改進RSA求解前k條SPTP的最短路徑。并且可以將算法擴展到動態網絡或帶有時間窗的網絡結構中，增加算法在實際應用中的價值。

參考文獻：

［1］Dijkstra E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik，1959，1（1）： 269-271.

［2］楊傳印，黃瑋，薛少聰，等. 基于優先隊列的時變網絡最短路徑算法［J］. 計算機應用研究，2019，36（5）： 1403-1408. （Yang Chuan-yin，Huang Wei，Xue Shaocong，et al. Shortest path algorithm for time-varying networks based on priority queue［J］. Application Research of Computers，2019，36（5）： 1403-1408.）

［3］葉穎詩，魏福義，蔡賢資. 基于并行計算的快速Dijkstra算法研究［J］. 計算機工程與應用，2020，56（6）： 58-65. （Ye Yingshi，Wei Fuyi，Cai Xianzi. Research on fast Dijkstra algorithm based on parallel computing［J］. Computer Engineering and Application，2020，56（6）： 58-65.）

［4］Bajaj C P. Some constrained shortest-route problems［J］. Unternehmensforschung，1971，15（1）： 287-301.

［5］Ferone D. The shortest path tour problem and its variants［D］. Italy： University of Naples Federico II，2017.

［6］Han Bo，Gopalakrishnan V，Ji Lusheng，et al. Network function virtua-lization： challenges and opportunities for innovations［J］. IEEE Communications Magazine，2015，53（2）： 90-97.

［7］王進文，張曉麗，李琦，等. 網絡功能虛擬化技術研究進展［J］. 計算機學報，2019，42（2）： 185-206. （Wang Jinwen，Zhang Xiaoli，Li Qi，et al. Research progress of network function virtualization technology ［J］. Chinese Journal of Computers，2019，42（2）： 185-206.）

［8］Abdelwahab S，Hamdaoui B，Guizani M，et al. Network function virtua-lization in 5G［J］. IEEE Communications Magazine，2016，54（4）： 84-91.

［9］Sasabe M，Hara T. Shortest path tour problem based integer linear programming for service chaining in NFV networks［C］// Proc of the 6th IEEE Conference on Network Softwarization. Piscataway，NJ： IEEE Press，2020： 114-121.

［10］鐘百勝，姜利群. 軟件定義網絡中利用IMKVS結合NFV的分布式網絡負載均衡策略［J］. 計算機應用研究，2019，36（5）： 1504-1509. （Zhong Baisheng，Jiang Liqun. Software defined distributed network load balancing strategy using IMKVS combined with NFV in network ［J］. Application Research of Computers，2019，36（5）： 1504-1509.）

［11］Bhat S，Rouskas G N. Service-concatenation routing with applications to network functions virtualization［C］// Proc of the 26th International Conference on Computer Communication and Networks. Piscataway，NJ： IEEE Press，2017： 1-9.

［12］李暢，徐琪，李光磊，等. 基于服務功能鏈的多域安全服務按需適配方法［J］. 計算機工程與應用，2018，54（21）： 56-64，119. （Li Chang，Xu Qi，Li Guanglei，et al. On demand adaptation method of multi domain security services based on service function chain［J］. Computer Engineering and Application，2018，54（21）： 56-64，119.）

［13］Bolla R，Lombardo C，Bruschi R，et al. DROPv2： energy efficiency through network function virtualization ［J］. IEEE Network，2014，28（2）： 26-32.

［14］Festa P. Complexity analysis and optimization of the shortest path tour problem ［J］. Optimization Letters，2012，6（1）： 163-175.

［15］Festa P，Guerriero F，Laganà D，et al. Solving the shortest path tour problem［J］. European Journal of Operational Research，2013，230（3）： 464-474.

［16］Bertsekas D P. Dynamic programming and optimal control［M］. ［S.l.］： Athena Scientific，2012.

［17］Hu Xiaobing，Wang Ming，Leeson M S，et al. Deterministic agent-based path optimization by mimicking the spreading of ripples［J］. Evolutionary Computation，2016，24（2）： 319-346.

［18］Gember A，Krishnamurthy A，John S S，et al. Stratos： a network-aware orchestration layer for middleboxes in the cloud ［EB/OL］. （2014-03-11）. https：//arxiv.org/abs/1305.0209.

［19］Newman M E J. The structure and function of complex networks［J］. SIAM Review，2003，45（2）： 167-256.

［20］倪玲霖，史峰. 多分配快遞軸輻網絡的樞紐選址與分配優化方法［J］. 系統工程理論與實踐，2012，32（2）： 441-448. （Ni Linglin，Shi Feng. Hub location and allocation optimization of multiple allocation hub-and-spoke express networks［J］. System Engineering Theory and Practice，2012，32（2）： 441-448.