淺議求解最短路徑問題的兩種算法

高 嵐

（吉林工程技術(shù)師范學(xué)院信息工程學(xué)院，吉林 長春 130052）

0 引言

最短路徑問題是網(wǎng)絡(luò)分析中最基本的組合優(yōu)化問題之一，在公交路線網(wǎng)絡(luò)規(guī)劃中應(yīng)用廣泛。因此，實際公交線網(wǎng)優(yōu)化設(shè)計中，路徑選擇算法成為一個重要研究課題，它直接關(guān)系到交通網(wǎng)絡(luò)效率、傳輸延遲和吞吐量等主要技術(shù)性能指標(biāo)。

早在20世紀(jì)初，最短路徑這一重要問題就已得到人們的高度重視，當(dāng)時有許多科學(xué)家研究這一問題的求解方法，但直到1959年荷蘭計算機(jī)科學(xué)家Dijkstra（迪加斯特拉）才給出這一問題求解的基本思想，成為一代經(jīng)典。當(dāng)時的Dijkstra 提出的這一算法主要解決的是從固定的一點到其他各點的最短路徑問題。但實際生活中要求解的可能是任意兩點間的最短距離，可采用Floyd（弗洛伊德）算法。本文通過將兩種算法進(jìn)行一些對比討論，得出關(guān)于兩種算法效率和適用問題的一些結(jié)論。

1 最短路徑問題

最短路徑問題是圖論中的基本問題。在賦權(quán)圖中，找出兩點間總權(quán)和最小的路徑就是最短路徑問題。最短路徑算法包括指定頂點對之間的最短路徑算法和所有頂點間的最短路徑算法，前者對于運輸?shù)暮侠砘哂兄匾碚撘饬x，而后者的意義在于選擇合理的中轉(zhuǎn)中心，使得總費用最少。在圖論中最典型的兩種求最短路徑算法分別是Dijkstra 算法和Floyd 算法。

2 Dijkstra 算法

2.1 算法基本思想

每次新擴(kuò)展一個距離最短的點，更新與其相鄰點間距離。當(dāng)所有邊的權(quán)都為正時，由于不會存在一個距離更短的沒有擴(kuò)展過的點，所以這個點的距離不會再被改變，因而保證了算法的正確性。根據(jù)這個原理，采用Dijkstra 算法求解最短路的圖不能有負(fù)權(quán)邊，因為擴(kuò)展到負(fù)權(quán)邊的時候會產(chǎn)生更短的距離，有可能破壞已經(jīng)更新的點距離不會改變的性質(zhì)。

2.2 Dijkstra 算法思想在物流配送中的應(yīng)用

采用圖論中的最短路徑算法Dijkstra 算法來建立物流配送路徑選擇模型，主要思想是從代表兩個頂點的距離開始，每次插入一個頂點比較任意兩點之間的已知最短路徑和插入頂點作為中間頂點時兩點間的最短路徑，得到的最終的權(quán)矩陣就反映了所有頂點間的最短距離信息。最短距離者作為費用最小者，即最佳的物流配送選址位置。

3 Floyd 算法

3.1 算法基本思想

通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。

從圖的帶權(quán)鄰接矩陣A＝[a(i，j)]n×n 開始，遞歸地進(jìn)行n 次更新，即由矩陣D(0)＝A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i 行j 列元素便是i 號頂點到j(luò) 號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path 來記錄兩點間的最短路徑。

3.2 Floyd 算法在選址問題中的應(yīng)用

某城市考慮建立區(qū)域內(nèi)二次供水中轉(zhuǎn)站。在選址問題中，點表示可供選址，其間連線表示運輸費用，其需求點之間運費如圖1 所示。在選址中，要求該中轉(zhuǎn)站到其他站點的距離最短，即運輸費用最少，通過運用求解最短路徑的Floyd 算法可求出該網(wǎng)點布局的最佳中轉(zhuǎn)站。

圖1 網(wǎng)絡(luò)拓?fù)?/p>

由計算可知，a 到其他點的費用和為C(a)＝33，同理C(b)＝27，C(c)＝18，C(d)＝21，C(e)＝33，比較可知c 到其他各點的費用最小。因此本例從經(jīng)濟(jì)性考慮，選c 點為中轉(zhuǎn)站最優(yōu)。

4 討論

典型的最短路徑求解算法Dijkstra 算法和Floyd 算法各有所長。Dijkstra 算法可為任一源節(jié)點找出與其它所有節(jié)點的最短路徑，是目前公認(rèn)的較好的最短路徑算法，但由于它遍歷計算的節(jié)點很多，所以效率低。Floyd 算法是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法，是一種動態(tài)規(guī)劃算法，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單，但是Floyd 算法計算最短路徑時時間復(fù)雜比較高，不適合計算大量數(shù)據(jù)。

綜上，求解單源點無負(fù)權(quán)邊最短路徑可采用Dijkstra 算法，而求所有點最短路徑應(yīng)用Floyd 算法。對于稀疏圖，采用n 次Dijkstra 算法比較出色，對于稠密圖，適用Floyd 算法。

5 結(jié)束語

本文通過對比兩種求解最短路徑算法的設(shè)計思想、求解過程、應(yīng)用實例，討論了算法的特點及適用領(lǐng)域。了解算法求解問題的差異，針對不同類型問題采取對應(yīng)的求解算法，將大大提升解決問題的效率，對實際生產(chǎn)生活起到重要作用。

［1］辛建亭，胡萍.圖論在通訊網(wǎng)中的應(yīng)用[J].2009，3.

［2］凡金偉，呂康.基于Dijkstra 算法在物流配送中的應(yīng)用[J].電腦編程技巧與維護(hù)，2009(4)：39-45.

［3］鄧春燕.兩種最短路徑算法的比較[J].電腦知識與技術(shù)，2008(12)：511-512.

［4］徐鳳生.求最短路徑的新算法[J].計算機(jī)工程與科學(xué)，2006，2.

［5］殷劍宏，吳開亞.圖論及其算法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2005.

［6］陳玉華.淺談圖論在現(xiàn)實生活中的應(yīng)用[J].云南省教育學(xué)院學(xué)報，2004.

［7］王燕，蔣笑梅.配送中心全程規(guī)劃[M].北京：機(jī)械工業(yè)出版社，2004.

［8］項榮武，劉艷杰，胡忠盛.圖論中最短路徑問題的解法[J].沈陽航空工業(yè)學(xué)院學(xué)報，2004.