Floyd多源最短路徑算法的并行化研究

龔寧靜

（湖北警官學院信息技術系，武漢 430034）

0 引言

人們經常在計算機中使用圖結構來分析和處理實際生活中那些有多對多映射關系的數據。圖結構中若頂點A經過某些邊或弧可以到達頂點B，那么由權值之和最小的邊或弧組成的路徑就是頂點A到頂點B的最短路徑。我們經常使用最短路徑算法來解決實際生活中遇到的很多問題，比如：地圖導航、物流管理、交通控制、通信網絡、社交網絡，等等。

圖的最短路徑問題又分為單源最短路徑和多源最短路徑兩種應用場景。單源最短路徑是以圖結構中某一頂點為源點，求從源點出發到圖中其它所有頂點的最短路徑。多源最短路徑是求解圖結構中任意兩個頂點之間的最短路徑［1］。以地圖導航為例：假如導航APP 只為一個用戶服務，且用戶以家作為源點。那么導航可以使用單源最短路徑算法為此用戶計算出從他家到其它任何目的地的最短路線。但實際上導航APP 面對的用戶成千上萬，因此APP 最終是使用多源最短路徑算法同時為所有向它請求的用戶給出導航服務。Floyd 多源最短路徑算法最大的缺點是執行效率低，時間復雜度為O（n3）。因此當圖結構中頂點、邊或弧的數量較多時，計算時間會大幅度增加，難以滿足實時響應的需求［2-4］。針對Floyd 算法的這一缺點，本文從并行計算的角度來找出該算法的優化辦法，降低時間復雜度，提高執行效率［5-6］。

1 Floyd多源最短路徑的現有算法

Floyd 算法求解圖結構中任意兩個頂點之間的最短路徑。假設有一個圖結構如圖1 所示（圖中包含5 個頂點、9 條弧，每條弧的權值為標在該弧旁邊的數字）。

圖1 待求多源最短路徑的圖結構

如果要對該圖結構求解多源最短路徑，設圖中頂點數為n，那么每個頂點都能求出n-1 條最短路徑，圖中一共可以求出n（n-1）條最短路徑。我們可以把所有的最短路徑存儲在一個n行n列的矩陣中，如圖2所示。圖2中一共n2個矩陣元素，除去主對角線元素外，剩下的n（n-1）個元素剛好可以存儲和對應每一條最短路徑。比如矩陣中B行D列（1 行3 列）的元素對應的就是頂點B到頂點D的最短路徑。

圖2 存儲所有最短路徑的矩陣

Floyd 算法求所有最短路徑其實是利用動態規劃同時尋找給定加權圖中任意兩頂點之間的最短路徑。對于每一對頂點的最短路徑的尋找，使用插點法來逐個比較可選路徑，通過保留較小者、淘汰較大者來刷新當前最短路徑?？蛇x路徑通過枚舉插入的不同頂點來生成。假設矩陣用二維數組D來實現，那么頂點i 到頂點j 的最短路徑在尋找過程中的一次比較和刷新算法如下：

算法1：當插入頂點為u時，i到j最短路徑的更新

Floyd 算法會同時對所有最短路徑進行比較和刷新，因此當枚舉的插入點為頂點u時，其它最短路徑也會比較自己的當前最短路徑和插入了頂點u后的路徑哪個更短，用更短的值來作為最新的當前最短路徑。這部分的完整代碼如下：

算法2：當插入頂點為u時，矩陣D的一次迭代

以上代碼通過枚舉插入頂點u，對保存在矩陣中的所有最短路徑都進行了一次比較和刷新。我們可以把這一部分代碼看成是矩陣D的一次迭代計算。代碼塊的時間復雜度為O（n2）。為了無遺漏地找出所有的可選路徑加以比較，圖中所有的頂點都需要被枚舉成插入點。因此還需要在上面代碼塊的外層再套一個循環來實現將圖中所有頂點枚舉成插入點。初始狀態下矩陣D其實就是該圖結構的鄰接矩陣。完整算法的時間復雜度為O（n3）。Floyd 關于矩陣D的核心算法如下：

算法3：Floyd關于矩陣D的計算

Floyd 現有算法的時間復雜度太高，用該算法來處理現實中的實際問題時，對應的圖結構往往是頂點和弧的數量巨大的稠密圖。在數據量大的情況下，算法的執行效率會顯著降低，難以保證響應的時間。許多實際應用在這種情況下會放棄Floyd算法使用其它算法來替代［7］。

2 一次矩陣迭代的并行計算實現

能不能找到辦法降低Floyd 算法的時間復雜度從而提高執行效率呢？在分析Floyd 算法的代碼時，我們發現算法2 描述的當插入的頂點為u時，整個矩陣D的一次迭代計算其實是按照先后順序一條一條更新了所有最短路徑。因此矩陣D的一次迭代執行了n2次循環操作，每次循環只修改了矩陣中一個元素，其它元素處于等待狀態。其它元素能不能不等待，也同步執行更新呢？在矩陣D的一次迭代中，每一條最短路徑的更新都只會比較自己現有的最短路徑和插入頂點u生成的路徑哪條更短？計算過程不依賴其它路徑的更新。因此矩陣D中每個矩陣元素的更新都是可以同步進行的。

有了以上的分析，我們可以通過并行計算的角度來重寫算法2 的代碼，將矩陣D的一次迭代用矩陣的運算方式實現處理，在一次運算的時間內將矩陣中所有元素同步更新到位。

為了能順利地進行矩陣點運算，也就是兩個矩陣中對應位置元素的運算，首先要根據矩陣D進行一些變化，生成幫助運算的輔助矩陣。算法2 中每一條最短路徑D［i］［j］都要與插入頂點u后生成的路徑D［i］［u］+D［u］［j］比較大小。在對整個矩陣D更新時，i和j的取值范圍是從0到n-1，而u的取值固定不變。因此，我們要構造一個矩陣D,D'中每個元素D'［i］［j］的值等于D矩陣中對應的D［i］［u］+D［u］［j］的值。又因為D'［i］［j］是通過D［i］［u］+D［u］［j］得到的，所以我們先構造兩個矩陣Dr和Dc，使Dr和Dc相加能得到D'。Dr中每i行的元素都應該是D矩陣中的D［i］［u］，Dc中每j列的元素都應該是D矩陣中的D［u］［j］。假設插入頂點u為第0個頂點，那么矩陣Dr可以取矩陣D的第0 列并平鋪成5列得到。矩陣Dc可以取矩陣D的第0 行并平鋪成5行得到。

通過圖3 我們可以看到，通過矩陣D得到的Dr和Dc中每個元素均來自矩陣D。

圖3 構造矩陣D'的矩陣Dr和Dc

矩陣Dr和Dc中的任意元素Dij表示該元素來自矩陣D的第i行第j列，是矩陣D中D［i］［j］。所以當Dr和Dc進行矩陣相加時，對應位置的元素直接做加法。比如Dr中第4 行第3 列的元素D40與Dc中第4行第3列的元素D03位置對應，這兩個元素的值相加其實就是矩陣D中的D［4］［0］+D［0］［3］，相加的結果就是頂點4 到頂點3 在插入了頂點0 后生成的路徑。如果我們用矩陣D'來保存Dr和Dc相加的結果，按照矩陣加法的規則，剛才兩個元素相加的結果會被保存在結果矩陣的第4 行第3 列，也就是矩陣D'的D'［4］［3］中。由此，我們構造出了矩陣D',D'中每個元素D'［i］［j］的值等于D矩陣中對應的D［i］［0］+D［0］［j］的值。

根據以上分析，我們可以從并行計算的角度重寫算法2，形成算法4。由于這里描述的是基于并行計算的步驟，而MATLAB 和Python 編程環境下可以很方便地進行并行處理，因此該算法使用MATLAB 的編程語法來進行描述。將之前的算法2 和基于并行計算的算法4 相比較，這兩個算法都是實現矩陣D的一次迭代，在插入點為頂點u時對矩陣中所有元素（矩陣中保存的所有當前最短路徑）進行比較和刷新。算法2的時間復雜度為O（n2），而算法4 的時間復雜度為O（1）。通過對Floyd 中一次矩陣迭代的并行計算實現，算法4 大大降低了這一步驟的時間復雜度，從平方階直接降到了常數階。

算法4：當插入頂點為u時，一次矩陣迭代的并行計算

3 Floyd算法的并行計算實現

接下來，我們通過算法5 給出Floyd 算法中關于矩陣D的并行計算的核心算法。和算法4一樣，這里使用MATLAB 編程語法來描述該算法。初始狀態時，矩陣D是待求多源最短路徑的圖結構對應的鄰接矩陣。u的初始取值為1，表示首次枚舉出的插入點是頂點1。通過D（u，:）取出矩陣D中的第u行，再通過repmat（ ，n，1）將這一行平鋪n行，得到矩陣Dc。通過D（：，u）取出矩陣D中的第u列，再通過repmat（ ，1，n）將這一列平鋪n列，得到矩陣Dr。通過Dr+Dc得到D'，用來保存每一條當前最短路徑的出發頂點和目的頂點間如果插入了頂點u后生成的路徑長度。通過D= min(D,Dr+Dc)比較D和D'中對應位置的兩個元素（兩條擁有相同出發頂點和目的頂點的路徑）的值，用較短的路徑來刷新每一個元素表示的當前最短路徑。因此一次循環結束后，矩陣D保存的所有最短路徑刷新一遍。下一次循環u的值加1，枚舉下一個頂點作為插入點，再來對矩陣D進行下一次整體刷新。當u取值從1 到n全部枚舉完畢后，矩陣D的最后狀態保存的就是要求出的n（n-1）條最短路徑的路徑長度。這里算法只關注了最短路徑長度矩陣D的處理，省略了對最短路徑經過情況矩陣的處理。

算法5：Floyd 算法關于矩陣D的完整并行計算

Floyd 算法經過并行計算的重寫后，整體的時間復雜度由原來的O（n3）降低到O（n）。效率得到了大幅度的提升。

4 結語

本文針對現有的Floyd 多源最短路徑算法執行效率低下，無法在數據量大的稠密圖上高效運行這一問題，從并行計算的角度著手研究，將算法中插入點給定時進行一次矩陣迭代并逐條刷新所有當前最短路徑的順序過程優化為基于并行計算的同步刷新過程。該優化使得Floyd算法的時間復雜度由原來的立方階降低為線性階，從理論上提高了算法的執行效率。當然該研究并不完善，后續將會把記錄最短路徑經過情況的矩陣也納入進來，進行進一步優化。