最短路徑算法研究

李魯平

摘要：最短路徑問(wèn)題是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。用于解決最短路徑問(wèn)題的算法被稱做“最短路徑算法”，有時(shí)被簡(jiǎn)稱作“路徑算法”。最常用的路徑算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要對(duì)其中的兩種：Dijkstra和Floyd-Warshall進(jìn)行研究和分析實(shí)現(xiàn)。

關(guān)鍵詞：算法；動(dòng)態(tài)規(guī)劃；最短路徑；編程開(kāi)發(fā)

0 引言

在日常生活中，我們?nèi)绻枰３Ｍ礎(chǔ)地區(qū)和B地區(qū)之間，我們最希望知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中，那一條路徑的路途最短。最短路徑問(wèn)題是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：

（1）確定起點(diǎn)的最短路徑問(wèn)題：即已知起始結(jié)點(diǎn)，求最短路徑的問(wèn)題。

（2）確定終點(diǎn)的最短路徑問(wèn)題：與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。

（3）確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。

（4）全局最短路徑問(wèn)題：求圖中所有的最短路徑。

用于解決最短路徑問(wèn)題的算法被稱做“最短路徑算法”，有時(shí)被簡(jiǎn)稱作“路徑算法”。最常用的路徑算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、SPFA算法。Floyd-Warshall算法是求多源、無(wú)負(fù)權(quán)邊的最短路，用矩陣記錄圖，時(shí)效性較差，時(shí)間復(fù)雜度O（V^3）。Dijkstra算法是求單源、無(wú)負(fù)權(quán)的最短路的算法，時(shí)效性較好，時(shí)間復(fù)雜度為O（V*（V+E）），可以用優(yōu)先隊(duì)列進(jìn)行優(yōu)化，優(yōu)化后時(shí)間復(fù)雜度變?yōu)镺（v*lgn）。Bellman-Ford算法求單源最短路，可以判斷有無(wú)負(fù)權(quán)回路（若有，則不存在最短路），時(shí)效性較好，時(shí)間復(fù)雜度O（V*E）。SPFA算法是對(duì)Bellman-Ford算法的隊(duì)列優(yōu)化，時(shí)效性相對(duì)好，時(shí)間復(fù)雜度O（kE）。本文主要研究Dijkstra和Floyd-Warshall算法細(xì)節(jié)。

1. Dijkstra算法

Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發(fā)現(xiàn)的單源最短路徑算法，即在圖中求出給定頂點(diǎn)到其它任一頂點(diǎn)的最短路徑。在弄清楚如何求算單源最短路徑問(wèn)題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。該性質(zhì)描述為：如果P（i，j）={Vi...Vk...Vs...Vj}是從頂點(diǎn)i到j(luò)的最短路徑，k和s是這條路徑上的一個(gè)中間頂點(diǎn)，那么P（k，s）必定是從k到s的最短路徑。

證明該最優(yōu)子結(jié)構(gòu)為，假設(shè)P（i，j）={Vi...Vk…Vs...Vj}是從頂點(diǎn)i到j(luò)的最短路徑，則有P（i，j）=P（i，k）+P（k，s）+P（s，j）。而P（k，s）不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P'（k，s），那么P'（i，j）=P（i，k）+P'（k，s）+P（s，j）

由上述性質(zhì)可知，如果存在一條從i到j(luò)的最短路徑（Vi...Vk，Vj），Vk是Vj前面的一頂點(diǎn)。那么（Vi...Vk）也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長(zhǎng)度遞增，逐次生成最短路徑的算法。譬如對(duì)于源頂點(diǎn)V0，首先選擇其直接相鄰的頂點(diǎn)中長(zhǎng)度最短的頂點(diǎn)Vi，那么當(dāng)前已知可得從V0到達(dá)Vj頂點(diǎn)的最短距離dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根據(jù)這種思路，假設(shè)存在G=，源頂點(diǎn)為V0，U={V0}，dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個(gè)頂點(diǎn)：

1.從V-U中選擇使dist[i]值最小的頂點(diǎn)i，將i加入到U中；

2.更新與i直接相鄰頂點(diǎn)的dist值。（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）

3.知道U=V，停止。

2. Floyd-Warshall算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O（N3），空間復(fù)雜度為O（N2）。

Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語(yǔ)言來(lái)描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問(wèn)題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋。

從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，一是直接從i到j(luò)，二是從i經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis（i，j）為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis（i，k） + Dis（k，j） < Dis（i，j）是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis（i，j） = Dis（i，k） + Dis（k，j），這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis（i，j）中記錄的便是i到j(luò)的最短路徑的距離。

3. 總結(jié)

Dijkstra算法是解決單源最短路徑問(wèn)題的貪心算法，其基本思想是設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來(lái)擴(kuò)充這個(gè)集合。對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O（n）時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O（n2）時(shí)間。而Floyd算法的原理是動(dòng)態(tài)規(guī)劃，時(shí)間復(fù)雜度為O（n3），空間復(fù)雜度為O（n2），在實(shí)際算法中，為了節(jié)約空間，可以直接在原來(lái)空間上進(jìn)行迭代，這樣空間可降至二維。為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法，以及它的堆優(yōu)化版本。

參考文獻(xiàn)

[1] 黃國(guó)瑜、葉乃菁，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2001年8月第1版

[2] 最短路徑，http：//baike.baidu.com/view/349189.htm？func=retitle

[3] 李春葆，數(shù)據(jù)結(jié)構(gòu)教程，清華大學(xué)出版社，2005年1月第1版

[3] Dijkstra算法，http：//baike.baidu.com/view/7839.htm