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

龔寧靜

（湖北警官學(xué)院信息技術(shù)系，武漢 430034）

0 引言

人們經(jīng)常在計(jì)算機(jī)中使用圖結(jié)構(gòu)來分析和處理實(shí)際生活中那些有多對(duì)多映射關(guān)系的數(shù)據(jù)。圖結(jié)構(gòu)中若頂點(diǎn)A經(jīng)過某些邊或弧可以到達(dá)頂點(diǎn)B，那么由權(quán)值之和最小的邊或弧組成的路徑就是頂點(diǎn)A到頂點(diǎn)B的最短路徑。我們經(jīng)常使用最短路徑算法來解決實(shí)際生活中遇到的很多問題，比如：地圖導(dǎo)航、物流管理、交通控制、通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)，等等。

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

1 Floyd多源最短路徑的現(xiàn)有算法

Floyd 算法求解圖結(jié)構(gòu)中任意兩個(gè)頂點(diǎn)之間的最短路徑。假設(shè)有一個(gè)圖結(jié)構(gòu)如圖1 所示（圖中包含5 個(gè)頂點(diǎn)、9 條弧，每條弧的權(quán)值為標(biāo)在該弧旁邊的數(shù)字）。

圖1 待求多源最短路徑的圖結(jié)構(gòu)

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

圖2 存儲(chǔ)所有最短路徑的矩陣

Floyd 算法求所有最短路徑其實(shí)是利用動(dòng)態(tài)規(guī)劃同時(shí)尋找給定加權(quán)圖中任意兩頂點(diǎn)之間的最短路徑。對(duì)于每一對(duì)頂點(diǎn)的最短路徑的尋找，使用插點(diǎn)法來逐個(gè)比較可選路徑，通過保留較小者、淘汰較大者來刷新當(dāng)前最短路徑。可選路徑通過枚舉插入的不同頂點(diǎn)來生成。假設(shè)矩陣用二維數(shù)組D來實(shí)現(xiàn)，那么頂點(diǎn)i 到頂點(diǎn)j 的最短路徑在尋找過程中的一次比較和刷新算法如下：

算法1：當(dāng)插入頂點(diǎn)為u時(shí)，i到j(luò)最短路徑的更新

Floyd 算法會(huì)同時(shí)對(duì)所有最短路徑進(jìn)行比較和刷新，因此當(dāng)枚舉的插入點(diǎn)為頂點(diǎn)u時(shí)，其它最短路徑也會(huì)比較自己的當(dāng)前最短路徑和插入了頂點(diǎn)u后的路徑哪個(gè)更短，用更短的值來作為最新的當(dāng)前最短路徑。這部分的完整代碼如下：

算法2：當(dāng)插入頂點(diǎn)為u時(shí)，矩陣D的一次迭代

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

算法3：Floyd關(guān)于矩陣D的計(jì)算

Floyd 現(xiàn)有算法的時(shí)間復(fù)雜度太高，用該算法來處理現(xiàn)實(shí)中的實(shí)際問題時(shí)，對(duì)應(yīng)的圖結(jié)構(gòu)往往是頂點(diǎn)和弧的數(shù)量巨大的稠密圖。在數(shù)據(jù)量大的情況下，算法的執(zhí)行效率會(huì)顯著降低，難以保證響應(yīng)的時(shí)間。許多實(shí)際應(yīng)用在這種情況下會(huì)放棄Floyd算法使用其它算法來替代［7］。

2 一次矩陣迭代的并行計(jì)算實(shí)現(xiàn)

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

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

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

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

圖3 構(gòu)造矩陣D'的矩陣Dr和Dc

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

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

算法4：當(dāng)插入頂點(diǎn)為u時(shí)，一次矩陣迭代的并行計(jì)算

3 Floyd算法的并行計(jì)算實(shí)現(xiàn)

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

算法5：Floyd 算法關(guān)于矩陣D的完整并行計(jì)算

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

4 結(jié)語

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