單源最短路徑問題

單源最短路徑問題（Single-Source Shortest Path Problem）是圖論中的一個基本問題，其目標是在一個帶有權重的圖中，從一個特定的源點（source）到圖中所有其他節點的最短路徑。這裡的「最短」通常是指路徑長度最小，而路徑長度是沿著邊的權重總和。

解決單源最短路徑問題的方法有很多，以下是一些常見的算法：

1. 迪傑斯特拉算法（Dijkstra's algorithm）：這是一個廣泛使用的算法，可以用來找到一個給定源點到圖中其他節點的最短路徑。它是一個貪心算法，每次選擇最靠近源點的未訪問節點進行擴展。迪傑斯特拉算法對於帶權重的有向圖和無向圖都適用，但它不適用於帶負權重的邊。

2. 佛洛伊德算法（Floyd's algorithm）：這個算法可以找到圖中任意兩個節點之間的最短路徑。它通過在所有可能的中間點上檢查路徑來工作，因此時間複雜度為 O(n^3)，其中 n 是圖中節點的數量。

3. 貝爾曼-福特算法（Bellman-Ford algorithm）：這個算法可以用來找到有向圖中從一個源點到所有其他節點的最短路徑，即使圖中包含負權重的邊。它通過檢查每條邊多次來確保沒有負循環。

4. Johnson's algorithm：這是一個用來找到無向圖中所有節點之間最短路徑的算法。它首先使用貝爾曼-福特算法來消除負循環，然後使用迪傑斯特拉算法來找到剩下的最短路徑。

這些算法在實際應用中都非常重要，它們可以用來解決各種問題，例如路由選擇、交通優化、操作系統和數據庫系統中的內存管理等。