單源最短路徑

單源最短路徑（Single-Source Shortest Paths）問題是在一個帶有權重的圖中，給定一個起點，找出到所有其他節點的最短路徑。這是一個廣泛研究的問題，有許多算法可以用來解決它，包括：

1. 迪傑斯特拉算法（Dijkstra's algorithm）：這是一個廣泛使用的算法，可以用來找到一個給定起點到所有其他節點的最短路徑。它對邊權非負的圖有效，並且在頂點數量較小的圖上運行速度很快。

2. 弗洛伊德算法（Floyd's algorithm）：這個算法可以找到任何兩個頂點之間的最短路徑，無論圖中有無負邊權。它的時間複雜度是 O(n^3)，其中 n 是圖中頂點的數量。

3. 貝爾曼-福特算法（Bellman-Ford algorithm）：這個算法可以用來找到有負邊權的圖中的單源最短路徑。它的時間複雜度是 O(VE)，其中 V 是頂點的數量，E 是邊的數量。

4. Johnson's algorithm：這個算法可以將 Bellman-Ford 算法的時間複雜度優化到 O(V^2)，用於有負邊權的圖。

這些算法通常用於路由選擇、交通優化和操作研究等領域。它們也可以用來解決其他相關的圖論問題，例如最小生成樹和單源最長路徑問題。