什麼是單源最短路徑問題

單源最短路徑問題（Single-Source Shortest Path Problem）是圖論中的一個基本問題，它的目標是在一個帶有權重的圖中，從一個特定的源點（source）到達所有其他頂點的最短路徑。這裡的「最短」通常是指路徑的總權重最小，而權重可以是距離、時間、成本或者其他可以累加的量。

給定一個圖 G = (V, E)，其中 V 是頂點集合，E 是邊集合，以及一個源點 s ∈ V，單源最短路徑問題的目標是為 G 中每個頂點 v 找到從 s 到 v 的最短路徑。

這個問題有許多實際應用，例如在交通網絡中找到從一個起點到所有其他目的地的最短路徑，或者在電網中找到從發電站到所有變電站的最低成本路徑。

解決單源最短路徑問題的算法包括：

1. 迪傑斯特拉算法（Dijkstra's algorithm）：這是一個廣泛使用的算法，它可以在有向或無向圖中找到單源最短路徑，但要求圖中邊的權重是非負的。

2. 佛洛伊德算法（Floyd's algorithm）：這個算法可以在任何帶有正權重或負權重的圖中找到單源最短路徑，但它需要 O(n^3) 時間，其中 n 是頂點數。

3. Bellman-Ford 算法：這個算法可以用來檢測圖中是否存在負權重循環，並且可以在有向圖或無向圖中找到單源最短路徑。

4. A* 搜尋算法：這是一個通用搜尋算法，可以用來解決單源最短路徑問題，但它需要一個好的估計函數來指引搜尋方向。

這些算法的選擇取決於圖的特性和所需的時間複雜度。例如，如果圖中沒有負權重循環，那麼迪傑斯特拉算法可能是最有效的；如果圖中有負權重，那麼可能需要使用 Bellman-Ford 算法或 A* 搜尋算法。