從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。
基本介紹
- 中文名：最短路徑算法
- 外文名：Shortest Path Algorithm
- 包括：Dijkstra算法、Floyd算法等
- 解決問題：最短路徑問題
- 定義：各邊上權值之和最小的一條路徑
- 屬於：圖論
定義,算法,
定義
最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：
（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）。
當是稀疏圖的情況時，此時E=V*V/lgV，所以算法的時間複雜度可為O（V^2）。若是斐波那契堆作優先佇列的話，算法時間複雜度，則為O（V*lgV + E）。
Floyd
求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間複雜度O(V^3)。
Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題。
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)。
設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為 ∞ 表示兩點之間沒有任何連線。
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為 ∞ 表示兩點之間沒有任何連線。
Bellman-Ford
求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），
時效性較好，時間複雜度O（VE）。
時效性較好，時間複雜度O（VE）。
Bellman-Ford算法是求解單源最短路徑問題的一種算法。
單源點的最短路徑問題是指：
給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。
給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。
與Dijkstra算法不同的是，在Bellman-Ford算法中，邊的權值可以為負數。
構想從我們可以從圖中找到一個環路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那么通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程式就會永遠運行下去。 而Bellman-Ford算法具有分辨這種負環路的能力。
SPFA
是Bellman-Ford的佇列最佳化，時效性相對好，時間複雜度O（kE）。（k<<V）。
與Bellman-ford算法類似，SPFA算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA算法通過維護一個佇列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重複的操作次數。
SPFA算法可以用於存在負數邊權的圖，這與dijkstra算法是不同的。
與Dijkstra算法與Bellman-ford算法都不同，SPFA的算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則算法實際上變為廣度優先遍歷，其時間複雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時算法退化為Bellman-ford算法，其時間複雜度為O(VE)。
SPFA算法在負邊權圖上可以完全取代Bellman-ford算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra算法，以及它的使用堆最佳化的版本。通常的SPFA算法在一類格線圖中的表現不盡如人意。
