最短路徑演算法

從某頂點出發，沿著圖的邊到達另一頂點所經過的路徑中，各邊上權值總和最小的一條路徑叫做最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。

定義

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

（1）決定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra演算法。 （建議學習：PHP影片教學）

（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）是解決任意兩點間的最短路徑的演算法，可以正確處理有向圖或負權的最短路徑問題。

Bellman-Ford

求單一源最短路，可以判斷有無負權迴路（若有，則不存在最短路），
時效性較好，時間複雜度O（VE）。

Bellman-Ford演算法是求解單源最短路徑問題的一種演算法。

SPFA

是Bellman-Ford的佇列最佳化，時效性相對好，時間複雜度O（kE）。 （k

與Bellman-ford演算法類似，SPFA演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。不同的是，SPFA演算法透過維護一個佇列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重複的操作次數。

更多PHP相關技術文章，請造訪PHP圖文教學欄位進行學習！

以上是最短路徑演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！