湛文紅

（首鋼工學(xué)院，北京100144）

1.引言

目前，在求網(wǎng)絡(luò)圖形最短路徑的問(wèn)題上主要有四種算法，它們是Dijkstra算法、逐次逼近算法、矩陣算法、Floyed算法，它們分別出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)、運(yùn)籌學(xué)、圖論等課程中。其中前兩種算法都是求圖上從某一點(diǎn)至另一點(diǎn)的最短路徑，而后兩種算法是求出網(wǎng)絡(luò)圖上所有節(jié)點(diǎn)之間的最短路徑。由于這些算法分別出現(xiàn)不同的學(xué)科課程中，因此人們不易將它們進(jìn)行統(tǒng)一的歸納總結(jié)與分析比較。

Dijkstra算法與逐次逼近算法解決的是從某一個(gè)節(jié)點(diǎn)到另一節(jié)點(diǎn)之間的最短路徑問(wèn)題，算法的時(shí)間復(fù)雜度是O(n2)。如果想得到每一對(duì)節(jié)點(diǎn)之間的最短路徑，則需要多次調(diào)用算法進(jìn)行計(jì)算。顯然，這種方式對(duì)于求網(wǎng)絡(luò)圖中每一對(duì)節(jié)點(diǎn)之間的最短距離就顯得過(guò)于麻煩。

矩陣算法與Floyed算法較好地解決了這方面的問(wèn)題，它可以通過(guò)算法的一次調(diào)用直接計(jì)算出網(wǎng)絡(luò)中每一對(duì)節(jié)點(diǎn)之間的最短路徑值，因而彌補(bǔ)了前兩種算法在這方面的不足。它們通過(guò)一個(gè)圖的權(quán)值矩陣求出每?jī)牲c(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i，j)]n×n開(kāi)始，逐漸擴(kuò)展，最終找到所有節(jié)點(diǎn)間的最短路徑。矩陣算法與Floyed算法的時(shí)間復(fù)雜度是O(n3)。

事實(shí)上，許多人混淆了后兩種算法，認(rèn)為它們是同一個(gè)算法，原因是它們不但功能相同，而且都是采用矩陣運(yùn)算的形式進(jìn)行最短路徑的求解。其實(shí)，它們?cè)谔幚矸椒ㄉ线€是有很大區(qū)別的，在此基礎(chǔ)上分析它們的附加功能也是不同的。本文將著重對(duì)這兩種算法進(jìn)行分析與討論，以求在實(shí)際應(yīng)用中對(duì)讀者起到參考借鑒的作用。

2.矩陣算法與Floyed算法的分析與研究

2.1 兩種算法的說(shuō)明

2.1.1 矩陣算法

矩陣算法的主要思想是首先構(gòu)造初始距離矩陣，然后進(jìn)行逐次迭代。首先進(jìn)行第一次迭代，求出網(wǎng)絡(luò)圖中任意兩個(gè)節(jié)點(diǎn)之間最多經(jīng)過(guò)1個(gè)中間節(jié)點(diǎn)的最短距離；再進(jìn)行第二次迭代，求出任意兩個(gè)節(jié)點(diǎn)之間最多經(jīng)過(guò)3個(gè)中間節(jié)點(diǎn)的最短距離；如此進(jìn)行直至第k次迭代，求出任意兩個(gè)節(jié)點(diǎn)間最多經(jīng)過(guò)（2k-1）個(gè)中間節(jié)點(diǎn)的最短距離或當(dāng)相鄰兩次迭

⑥最終得到任意兩點(diǎn)間的最短路徑值及其相應(yīng)途經(jīng)的節(jié)點(diǎn)序列。

此算法適用于所有無(wú)向圖與有向圖。

本人為此編制了程序以解釋其原理。用以下有向圖實(shí)例（如圖1所示）來(lái)加以說(shuō)明：

(1)定義圖形

如圖2所示，其中表格內(nèi)的數(shù)值表示兩點(diǎn)間的權(quán)值，空位置處表明兩點(diǎn)之間沒(méi)有直接路徑。代結(jié)果相同的時(shí)候停止迭代過(guò)程。

圖1 實(shí)例

具體步驟：

①首先構(gòu)造距離矩陣Dn×n（以距離為權(quán)的權(quán)值矩陣）。矩陣給出了所有節(jié)點(diǎn)之間只經(jīng)過(guò)一步（一條邊）的最短距離。

②設(shè)置途經(jīng)的節(jié)點(diǎn)路徑矩陣Rn×n內(nèi)的所有元素rij(i，j=1…n)均為空字符。

③對(duì)距離矩陣進(jìn)行如下的迭代運(yùn)算：

D(r)=D(r-1)*D(r-1)=[dij]（第一次迭代r=1，以后逐次加1。）

式中：

n----網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)；

D(0)為初始的距離矩陣；

*----矩陣邏輯運(yùn)算符，dij=m in[dik+dkj]（k=1，2，3，…，n）。dik，dkj----距離矩陣D(r-1)中的元素，分別為上次迭代后節(jié)點(diǎn)i、k之間、節(jié)點(diǎn)k、j之間的最短距離。dij為本次迭代后節(jié)點(diǎn)i，j之間經(jīng)過(guò)k節(jié)點(diǎn)的最短距離（k=1，2，3，…，n）。

④保存本次迭代當(dāng)前最短路徑的途徑節(jié)點(diǎn)序列。具體方法是：

如果本次迭代計(jì)算出的當(dāng)前最短路徑為dij=dik+dkj，則進(jìn)行下面的操作：

如果為第一次迭代則令rij=“i k j”，否則，則令rij=rik&rkj(其中符號(hào)“&”為字符串連接運(yùn)算符)。

圖2 定義圖形

(2)生成網(wǎng)絡(luò)圖形鄰接矩陣（如表1所示）

表1 鄰接矩陣

表2 第一次迭代后結(jié)果

(3)第一次迭代

第一次迭代的結(jié)果是兩個(gè)節(jié)點(diǎn)之間最多跨接1個(gè)節(jié)點(diǎn)（如表2所示）。

注：其中“∞(n，m)”表示從n點(diǎn)到m點(diǎn)之間的距離為∞，以下相同。

(4)第二次迭代

表3 第二次迭代后結(jié)果

第二次迭代的結(jié)果是兩個(gè)節(jié)點(diǎn)之間最多跨接3個(gè)節(jié)點(diǎn)（如表3所示）。

(5)第三次迭代

第三次迭代的結(jié)果是兩個(gè)節(jié)點(diǎn)之間最多跨接5個(gè)節(jié)點(diǎn)。在本例中本次迭代與上次結(jié)果相同（如表3所示），此矩陣內(nèi)存儲(chǔ)的數(shù)據(jù)即為最終結(jié)果，迭代過(guò)程就此結(jié)束。

2.1.2 Floyed算法

具體算法描述：

Floyed算法的目的是求出具有n個(gè)節(jié)點(diǎn)的圖中每一對(duì)節(jié)點(diǎn)之間的最短路徑。算法思想是：

假設(shè)求節(jié)點(diǎn)vi到vj的最短路徑。如果從vi到vj有弧，則從vi到vj存在一條長(zhǎng)度為cost[i，j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。

首先考慮路徑(vi，v1，vj)是否存在（即判別弧(vi，v1)和(v1，vi)是否存在）。如果存在，則比較(vi，vj)和(vi，v1，vj)的路徑長(zhǎng)度取長(zhǎng)度，較短者為從vi到vj的中間節(jié)點(diǎn)的序號(hào)不大于1的最短路徑。

在此基礎(chǔ)上再考慮增加一個(gè)節(jié)點(diǎn)v2，也就是說(shuō)，如果（vi，…，v2）和（v2，…vj）分別是當(dāng)前找到的中間節(jié)點(diǎn)的序號(hào)不大于1的最短路徑，那么（vi，…，v2，…vj）就有可能是從vi到vj的中間頂點(diǎn)的序號(hào)不大于2的最短路徑。將vi與vj之間所有中間節(jié)點(diǎn)的序號(hào)不大于2的最短路徑和中間節(jié)點(diǎn)的序號(hào)不大于1的最短路徑進(jìn)行比較，選出最短的路徑，從而得到中間節(jié)點(diǎn)序號(hào)不大于2的最短路徑。

在此基礎(chǔ)上再考慮增加一個(gè)節(jié)點(diǎn)v3，繼續(xù)進(jìn)行試探，從而得到vi與vj之間的中間節(jié)點(diǎn)序號(hào)不大于2的最短路徑。

以此類推，直到增加最后一個(gè)節(jié)點(diǎn)，找到vi與vj之間的中間節(jié)點(diǎn)序號(hào)不大于n的最短路徑。

按此方法，可以同時(shí)求得各對(duì)節(jié)點(diǎn)間的最短路徑。

現(xiàn)通過(guò)一個(gè)實(shí)例結(jié)合本人用此算法的編制的程序說(shuō)明其處理過(guò)程。此算法本應(yīng)三重循環(huán)一氣呵成，但是為了演示并說(shuō)明處理過(guò)程，特在程序中設(shè)置了間斷點(diǎn)，以方便理解算法的原理。

演示步驟（篇幅所限，用圖表表示）：

(1)輸入兩點(diǎn)之間的權(quán)值（距離）（見(jiàn)圖1）；

(2)生成鄰接矩陣（見(jiàn)圖2）；

(3)處理序號(hào)為1的節(jié)點(diǎn)，結(jié)果如表5所示。

表5 Floyed算法處理序號(hào)為1的節(jié)點(diǎn)結(jié)果

（4）依次處理序號(hào)為2、3、4、5的節(jié)點(diǎn)。由于篇幅所限，僅列出5號(hào)節(jié)點(diǎn)處理后的結(jié)果如表6所示。

表6 Floyed算法處理序號(hào)為5的節(jié)點(diǎn)結(jié)果

至此，圖中每一對(duì)節(jié)點(diǎn)之間的最短路徑全部找到。

2.2 兩種算法的聯(lián)系與區(qū)別研究

(1)兩種算法的相同點(diǎn)

兩種算法均采用鄰接矩陣的方式來(lái)存儲(chǔ)原始權(quán)值、中間結(jié)果及最終結(jié)果，在尋找最短路徑的過(guò)程中都采用對(duì)矩陣內(nèi)數(shù)據(jù)元素進(jìn)行算術(shù)及邏輯運(yùn)算，從跨接1個(gè)節(jié)點(diǎn)的路徑開(kāi)始逐步擴(kuò)展，最終得到所有結(jié)點(diǎn)之間最短路徑的結(jié)果，兩種算法的時(shí)間復(fù)雜度均為O(n3)

(2)兩種算法的處理方法不同

矩陣算法在尋找最短路徑過(guò)程中采用逐步迭代的方式進(jìn)行，每次迭代可以找到任意兩點(diǎn)間跨接的節(jié)點(diǎn)個(gè)數(shù)在限定范圍內(nèi)的最短路徑。通過(guò)每次迭代最多跨接2k-1個(gè)節(jié)點(diǎn)（其中k為迭代的次數(shù)）的遞增順序，逐步求得兩點(diǎn)之間的最短路徑。這種算法在迭代的過(guò)程中不強(qiáng)調(diào)節(jié)點(diǎn)的順序，而主要把精力聚焦在跨接節(jié)點(diǎn)的個(gè)數(shù)上，隨著迭代次數(shù)的增加，跨接的節(jié)點(diǎn)數(shù)隨之增加，直到跨接的節(jié)點(diǎn)數(shù)達(dá)到可能的最大值，至此最短路徑全部找到。

Floyed算法在尋找最短路徑的過(guò)程中采用三重循環(huán)的方式進(jìn)行，運(yùn)算過(guò)程依賴于節(jié)點(diǎn)的序號(hào)，即先計(jì)算跨接1號(hào)節(jié)點(diǎn)的所有當(dāng)前最短路徑，再在此基礎(chǔ)上查詢跨接2號(hào)節(jié)點(diǎn)的當(dāng)前最短路徑，以此類推，最終找到跨接最后一個(gè)節(jié)點(diǎn)的最短路徑，至此找到所有最短路徑結(jié)果。

兩種算法雖然處理方式不同，但實(shí)踐證明都是科學(xué)有效的方法。

(3)探討兩種算法的附加功能

根據(jù)上述的分析可見(jiàn)，矩陣算法在尋找最短路徑過(guò)程中，第k次迭代的結(jié)果是得到最多跨接2k-1個(gè)節(jié)點(diǎn)（其中k為迭代的第次數(shù)）的最短路徑，逐步迭代后最終求所有節(jié)點(diǎn)間的最短路徑。這樣做的好處是處理過(guò)程清晰明確，而且具有實(shí)用價(jià)值。例如：在公交運(yùn)行查詢中，乘客可以找到最多換乘n次車的最短路徑。對(duì)于乘客來(lái)說(shuō)，兩地之間的最短路徑并不意味著最方便，顧客往往希望盡量少換車次但路徑盡可能短的情況。例如從A地到B地有幾種走法，第一種走法是只乘1輛車即可到達(dá)終點(diǎn)，汽車共行駛20km；第二種走法是中途換乘1次車，汽車最短行使15km；第三種走法是中途換乘3次車，汽車最短行駛12km。年老體弱的人可能選擇第一種方法，年輕人可能選擇第二或第三種方法。因?yàn)閾Q乘次數(shù)少而且距離相對(duì)較短，所以大多數(shù)人會(huì)舍棄距離更短的第三種走法而選擇第二種走法。運(yùn)用矩陣算法可以通過(guò)逐次迭代過(guò)程的中間結(jié)果告知乘客換乘的次數(shù)及相應(yīng)的最短路徑，以此方便乘客在乘車距離與換乘次數(shù)之間進(jìn)行平衡。又例如在貨物運(yùn)輸過(guò)程中，運(yùn)輸公司往往要在時(shí)間與距離兩個(gè)方面尋找平衡點(diǎn)，有些路段雖然距離近但路面質(zhì)量低或道路擁堵造成耗時(shí)多，而有些路段雖然距離遠(yuǎn)但行駛順暢耗時(shí)少，針對(duì)這種情況，矩陣算法可以向運(yùn)輸公司提供多種路徑選擇方式，以更為人性化的方式提供交通信息服務(wù)。

Floyed算法在尋找最短路徑的過(guò)程中采用三重循環(huán)的方式進(jìn)行，運(yùn)算過(guò)程依賴于節(jié)點(diǎn)的序號(hào)。這種方法程序?qū)崿F(xiàn)起來(lái)容易，但是處理過(guò)程相對(duì)來(lái)講沒(méi)有運(yùn)籌學(xué)的矩陣算法清晰，中間處理結(jié)果沒(méi)有什么實(shí)用價(jià)值，因而幾乎沒(méi)有可以應(yīng)用的附加功能。

(4)矩陣算法在數(shù)學(xué)解釋方面有助于對(duì)Floyed算法的理解

矩陣算法采用數(shù)學(xué)中矩陣運(yùn)算的方式進(jìn)行最短路徑的查找，邏輯清晰、推理嚴(yán)密，使人一目了然。

Floyed算法采用三重循環(huán)結(jié)構(gòu)逐個(gè)節(jié)點(diǎn)遞進(jìn)的方式完成最短路徑的查找，雖然在數(shù)學(xué)方法的支撐與論證方面有些欠缺，但通過(guò)對(duì)實(shí)際問(wèn)題的分析與邏輯判斷，迄今為止此算法仍然是科學(xué)有效的經(jīng)典算法。同時(shí)，矩陣算法在數(shù)學(xué)解釋方面有助于加深對(duì)Floyed算法的理解。

總之，最短路徑問(wèn)題可以采用不同的算法來(lái)解決，這些算法各有區(qū)別、各具千秋，在實(shí)際應(yīng)用的過(guò)程中要結(jié)合需求選擇恰當(dāng)?shù)乃惴?，以求?shí)用、高效、快捷。

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1987.

[2] 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及其應(yīng)用[M].北京：高教出版社，2004.

[3] 張炯民，竇亮，黃國(guó)興.數(shù)據(jù)結(jié)構(gòu)與算法教程[M].上海：華東師范大學(xué)出版社，2007.

[4] 胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社，2007.