最短路算法是一類用於在加權圖中找到任意兩點之間最短路徑的算法。這類算法通常用於解決圖論中的最短路徑問題。根據不同的套用場景和圖的特性，有多種最短路算法被提出，包括Dijkstra算法、Floyd-Warshall算法等。
Dijkstra算法：
基本思想：Dijkstra算法是一種貪心算法，它從源點開始，每次選擇距離源點最近的未訪問節點，並更新該節點到其他節點的最短距離。
適用場景：適用於邊權值為正數的圖，可以處理稠密圖和稀疏圖。
時間複雜度：O(n^2)，其中n是節點的數量。
代碼示例：見搜尋結果和。
Floyd-Warshall算法：
基本思想：Floyd-Warshall算法通過動態規劃的方式，枚舉所有節點對之間的最短路徑。它通過逐步構建中間節點集合，來找到任意兩點之間的最短路徑。
適用場景：適用於邊權值為非負數的圖，可以處理帶負權迴路的圖。
時間複雜度：O(n^3)，其中n是節點的數量。
代碼示例：見搜尋結果和。
堆最佳化版Dijkstra：
改進點：通過使用堆數據結構，可以更高效地選擇距離源點最近的未訪問節點，從而最佳化Dijkstra算法的時間複雜度。
適用場景：適用於邊權值為正數的圖，尤其適用於稠密圖。
時間複雜度：O(mlogn)，其中m是邊的數量。
代碼示例：見搜尋結果。
綜上所述，最短路算法的選擇取決於圖的特性和問題的需求。對於邊權值為正數的圖，Dijkstra算法和堆最佳化版Dijkstra算法較為適用；對於邊權值為非負數且可能存在負權迴路的圖，Floyd-Warshall算法更為合適。