最短路算法有哪些

最短路問題是圖論中的一個經典問題，它涉及到在給定的圖中找到兩點之間或一組點到另一組點之間的最短路徑。最短路算法用於解決這類問題。以下是一些最短路算法：

1. 迪傑斯特拉（Dijkstra）算法： Dijkstra 算法是一種用於查找圖中的一系列頂點之間的最短路徑的算法。它從圖中的一個特定的源點開始，並找到該源點到圖中所有其他頂點的最短路徑。該算法是一種貪婪算法，每次選擇未訪問的頂點中最接近源點的頂點進行擴展。

2. 弗洛伊德（Floyd）算法： Floyd 算法是一種用於查找所有頂點之間最短路徑的算法。它通過在兩個頂點之間插入第三個頂點來檢查最短路徑。這個算法的時間複雜度是 O(n^3)，其中 n 是圖中頂點的數量。

3. 貝爾曼-福特（Bellman-Ford）算法： Bellman-Ford 算法是一種用於查找有向圖中從一個頂點到所有其他頂點的最短路徑的算法。它通過反覆放鬆邊來找到最短路徑。這個算法可以檢測負權迴路，並且對於邊權為負的圖，它比 Dijkstra 算法更適用。

4. A 算法： A 算法是一種用於搜尋最優路徑的啟發式搜尋算法。它結合了廣度優先搜尋和啟發式函式來找到兩個頂點之間的最短路徑。A* 算法在許多套用中都非常有效，包括路徑規劃和拼寫檢查。

5. 約翰森（Johnson）算法： Johnson 算法是一種用於在有向圖中找到所有頂點對之間最短路徑的算法。它通過使用 Bellman-Ford 算法和 Dijkstra 算法的組合來找到最短路徑。

6. 單源最短路徑算法： 單源最短路徑問題是找到從一個特定源點到圖中所有其他頂點的最短路徑的問題。這個問題可以通過 Dijkstra 算法、Bellman-Ford 算法或 A* 算法來解決。

7. 多源最短路徑算法： 多源最短路徑問題是找到一組源點到所有其他頂點的最短路徑的問題。這個問題可以通過 Floyd 算法或 Johnson 算法來解決。

這些是最短路問題中的一些常用算法。選擇哪種算法取決於圖的特性、邊的權重以及所需的最短路徑的類型。