什麼是單源最短路徑

單源最短路徑（Single-Source Shortest Paths）問題是在一個帶有權重的圖中，給定一個起點頂點，找出到所有其他頂點的最短路徑。這裡的「最短」通常是指路徑上的邊權總和最小，但也可能是指其他類型的最優化條件，如最大流、最小費用流等。

在圖論中，最短路徑問題是一個基本的問題，它有許多實際應用，例如在交通網絡中尋找從一個地點到另一個地點的最快路線，或者在計算機網絡中找出數據包從一個路由器到另一個路由器的最低延遲路徑。

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

1. 迪傑斯特拉算法（Dijkstra's algorithm）：這是一個用於尋找有向或無向圖中一個源點到其他頂點的最短路徑的非貪婪算法。它可以在邊權是非負數的圖中找到單源最短路徑。

2. 佛洛伊德算法（Floyd-Warshall algorithm）：這個算法可以找到任意兩個頂點之間的最短路徑，無論是否有負邊權。

3. 貝爾曼-福特算法（Bellman-Ford algorithm）：這個算法可以找到單源最短路徑，即使圖中存在負邊權，但邊權的減少不能導致循環。

這些算法的時間復雜度從 O(V^2)（對於迪傑斯特拉算法和貝爾曼-福特算法，其中 V 是頂點數）到 O(V^3)（對於佛洛伊德算法）不等，具體取決於圖的大小和算法的選擇。在實際應用中，通常會根據圖的特性和要求的精度來選擇最適合的算法。