最短路徑算法研究

李魯平

摘要：最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要對其中的兩種：Dijkstra和Floyd-Warshall進行研究和分析實現。

關鍵詞：算法；動態規劃；最短路徑；編程開發

0 引言

在日常生活中，我們如果需要常常往返A地區和B地區之間，我們最希望知道的可能是從A地區到B地區間的眾多路徑中，那一條路徑的路途最短。最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：

（1）確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。

（2）確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。

（3）確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

（4）全局最短路徑問題：求圖中所有的最短路徑。

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

1. Dijkstra算法

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

證明該最優子結構為，假設P（i，j）={Vi...Vk…Vs...Vj}是從頂點i到j的最短路徑，則有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）

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

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

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

3.知道U=V，停止。

2. Floyd-Warshall算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復雜度為O（N3），空間復雜度為O（N2）。

Floyd算法是一個經典的動態規劃算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態規劃的角度看問題，我們需要為這個目標重新做一個詮釋。

從任意節點i到任意節點j的最短路徑不外乎2種可能，一是直接從i到j，二是從i經過若干個節點k到j。所以，我們假設Dis（i，j）為節點u到節點v的最短路徑的距離，對于每一個節點k，我們檢查Dis（i，k） + Dis（k，j） < Dis（i，j）是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設置Dis（i，j） = Dis（i，k） + Dis（k，j），這樣一來，當我們遍歷完所有節點k，Dis（i，j）中記錄的便是i到j的最短路徑的距離。

3. 總結

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

參考文獻

[1] 黃國瑜、葉乃菁，數據結構，清華大學出版社，2001年8月第1版

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

[3] 李春葆，數據結構教程，清華大學出版社，2005年1月第1版

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