最短路徑算法并行化策略的研究與實現

（武漢外國語學校，湖北武漢，430000）

最短路徑算法并行化策略的研究與實現

閔思晗,付逸飛

（武漢外國語學校，湖北武漢，430000）

現階段，隨著我國智能交通系統與通信系統的不斷發展完善，網絡新特性的出現，對于網絡中最短路徑問題研究具有非常重要的意義。本文主要選取幾種最短路徑標號串行算法，并在此基礎上分別通過網絡復制與網絡分割策略，對其最短路徑進行求解，從而實現最短路徑算法并行策略的研究。

最短路徑算法；并行計算；網絡復制；網絡分割

最短路徑算法是實現資源分配與路線設計優化的基礎，隨著信息科技的不斷完善與發展，現階段網絡最短路徑算法越來越多，不同的網絡環境與應用，需求具有不同特性的最短路徑算法，并行計算技術的不斷發展為節省計算時間提供了有效的計算路徑，不斷提高了交通網絡最短路徑問題的解決效率，實現大規模交通網絡最短路徑問題的解決。

圖1：有向圖G=(V,A)

1 最短路徑算法比較分析

1.1 標號算法

標號算法在目前的最短路徑算法中，占有非常重要的地位，它可以依照不同的節點，對策略進行相應的分析與處理。

例如圖一中的有向圖G=(V,A)，將節點1作為圖中的源點，常用的標號算法主要是指在該圖中，求解單個源點到其它各個源點的最短路徑，如該圖1所示，在建立過程中，每一個獨立的節點都具有不同信息分類，例如長度標號,父節點號及節點的當前狀態.

在迭代過程中，源點至節點的最短路徑中的上限值，主要在長度標號中保留，在最短路徑計算結束之時，長度標號成為該線路中唯一最短的路徑；在該有向圖中，其中位于節點之上的上一層節點標號，在父節點中保存；節點的當前狀態中的數值主要代表，其未訪問以及永久標號等狀態。

1.2 最具代表性的最短路徑標號算法的選取

現階段，我國對最短路徑算法的研究已逐漸趨于成熟，但目前多種多樣的最短路徑算法，在測試網絡中的效率以及各項性能都不完善，在本文中最短路徑標號算法的選取中，主要選取幾種具有代表性的算法來實現計算與求解。Bellman-Ford-Moore(BFM)（LC-1q）,D' Esopo-Pape（LC-2q），以及Dijkstra算法（LS）。

表一：三種最短路徑串行算法理論時間復雜性

這三種算法的性能理論具有相應差別，雖然LC算法，理論上的復雜性上界比較大，但在稀疏網絡中具有良好的應用性能，由于其自身的應用特性，因此人們對于其期望性能的預測，存在很大的困難性，但與之相反，LS具有良好的預測性。

2 最短路徑算法并行化策略的研究

2.1 網絡復制策略

在求解最短路徑的過程中，可以利用系統的主處理器，將網絡復制于各處理器中，網絡源點按照處理器個數進行相應劃分，并將其分配于各處理器中；之后各個處理器，將不同源點所計算出的不同最短路徑，發送至主處理器，進而實現對其的分析與整理。

在對各處理器中的不同源點進行分配時，應根據其間的計算負載平衡，對其進行平均分配，在對源點最短路徑進行計算時，各個處理器間不用進行信息的互換，因此一定程度上節省了所需時間，提高了工作效率。

2.2 網絡分割策略

網絡分割最短路徑算法，主要是指在分布式網絡中實現單源最短路徑的解決，在工作過程中，它首先可將系統中的整體網絡劃分為多個子網，同時將其均勻分配至各處理器中。在該網絡分割系統中，包括邊界節點以及內部節點，它們都是系統的重要組成部分，在該算法實施當中，必須要保持各處理器間的部分通信暢通。在利用該方法進行最短路徑求解的過程中，需要對邊界節點的標號進行系統的更新，在對其進行更新時，還應該將其整理成相應的消息，并將其發送給相鄰子網中的處理器，由該處理器對其進行計算。

2.2.1 網絡分割

在網絡分割時應該注意盡量的將邊界節點的數量降到最低，這樣可節省開支，同時對于子網中的負載量應使其趨于平衡，這樣才能盡量減少處理器在工作時的時間，提高其工作效率。交通網絡中可采用模擬退火算法，而隨機網格可以采用方形分割法。

模擬退火算法在算法中可以解決大規模的組合優化問題，可以有效解決最短路徑計算問題。具體算法如下所示：本文以邊界節點量與子網節點量間的方差建立函數（p代表分割后的子網數，nbi代表在第i個子網中所包含的邊界節點的個數，nb則代表總邊界節點數）

由以上公式可以得出在模擬退火算法方法中，當函數值達到最小時，各邊界節點與子網中節點數值差距較小，因此其可以最大化的滿足網格分割要求。

2.2.2 終止檢測分析

在利用并行標號算法的網格分割求解最短路徑時，其消息的轉換與交流，會造成時間的過度消耗，同步過程也會造成時間的損耗。終止檢測頻率，對計算途中的各個處理器的等待時間有很大影響，在本文終止檢測方法的選取中，主要采用令牌傳遞法，該方法不需對最優終止檢測頻率進行預測。

3 最短路徑算法分析

本實驗中主要采用并行函數庫編程，實現對最短路徑的計算，同時在計算過程中，利用6臺節點機實現對算法加速比以及其效率的檢驗，在測試網絡的選取中，主要應用了3個實際的道路網格以及3個隨機網格，在稀疏性質中保證二者的相似性，同時添加內部節點與邊緣節點之間的連接弧，從而使二者的特征更加相似。

算法加速比：本文采取的算法模式都屬于粗粒度并行算法。在此基礎下可以看出網絡復制策略以及網絡分割策略都有很好的加速比，同時LC與LS綜合比較，以由于串行算法自身的標點節點的選取以及刪除等造成的影響，使得LC的整體加速比優于LS，因此從而證實LC比LS更適用于并行化。兩種策略下運用機器以及相關源點對最短路徑加速比進行分析。

表二：兩種策略最短路徑并行加速比

根據上述表格變化趨勢分析，在實際路網以及隨機網格中，網絡復制加速比會隨著節點數的增加而變小，而網絡分割中其加速比會隨網絡規模的不斷增大而增大。因此說明大規模交通網中網絡分割比網絡復制并行算法更具有優越性。

算法可拓展性：兩種并行算法都具有很好的可拓展性，在網絡復制中，網絡規模越小其擴展性越好，在網格分割中則恰恰相反，因此證實了網絡分割，較適用于大規模網絡最短路徑求解。

4 結束語

綜上所述，現階段，我國對于最短路徑算法并行化策略的研究已逐漸趨于完善，對于最短路徑的算法也具有多種多樣性，本文在研究中主要選取了幾種效率較高的串行最短路徑標號算法，同時利用網絡復制與分割策略對其進行應用，從而進一步提升其計算效率，為交通運輸中最短路徑并行算法的選擇與應用提供相應的依據。

[1] 孫文彬,譚正龍,王江,周長江,何俊芳.最短路徑算法的并行化策略分析[J].地理與地理信息科學,2013,04:17-20.

[2] 盧照.基于城市路網最短路徑并行搜索算法的研究[D].陜西師范大學,2010.

[3] 郭紹忠,王偉,周剛,胡艷.基于GPU的單源最短路徑算法設計與實現[J]. 計算機工程,2012,02:42-44.

[4] 張鐘.大規模圖上的最短路徑問題研究[D].中國科學技術大學,2014.

Research and implementation of the parallel strategy of shortest path algorithm

Min Sihan,Fu Yifei
(Wuhan foreign language school,Wuhan,Hubei,430000)

At present,with the continuous development of the intelligent transportation system and communication system in our country,the emergence of the new features of the network is very important for the research of the shortest path problem in the network.In this paper,we select some of the shortest path label serial algorithm,and on this basis,respectively,through the network replication and network segmentation strategy,the shortest path to solve the problem,so as to achieve the shortest path algorithm parallel strategy.

shortest path algorithm;parallel computing;network replication;network partition

閔思晗（1998-），女，武漢外國語學校高三在讀，

付逸飛（1999-），男，武漢外國語學校高二在讀