最短路徑算法

定義

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：

（1）確定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。

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

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

（4）全局最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。

Dijkstra

求單源、無負權的最短路。時效性較好，時間複雜度為O（V*V+E）。源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。

當是稀疏圖的情況時，此時E=V*V/lgV，所以算法的時間複雜度可為O（V^2）。若是斐波那契堆作優先佇列的話，算法時間複雜度，則為O（V*lgV + E）。

Floyd

求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間複雜度O(V^3)。

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題。

Floyd-Warshall算法的時間複雜度為O(N^3)，空間複雜度為O(N^2)。

Floyd-Warshall的原理是動態規劃：

設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。

若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；

若最短路徑不經過點k，則Di,j,k = Di,j,k-1。

因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在實際算法中，為了節約空間，可以直接在原來空間上進行疊代，這樣空間可降至二維。

Floyd-Warshall算法的描述如下：

for k ← 1 to n do

for i ← 1 to n do

for j ← 1 to n do

if (Di,k + Dk,j < Di,j) then

Di,j ← Di,k + Dk,j;

其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連線。