最短路問題定式化

最短路問題（Shortest Path Problem）是圖論中的一個基本問題，它的目標是在給定的圖中找到兩個頂點之間的最短路徑。最短路徑通常是指路徑長度最小的路徑，這裡的路徑長度是指路徑上邊條數目的總和。最短路問題可以分為單源最短路問題（Single-Source Shortest Path Problem）和所有對點最短路問題（All-Pairs Shortest Path Problem）。

單源最短路問題是指給定一個圖和一個源點，找出從這個源點到其他所有點的最短路徑。所有對點最短路問題則是指找出圖中任意兩個頂點之間的最短路徑。

最短路問題可以定義為以下形式：

給定一個有向圖G = (V, E)，其中V是頂點集，E是邊集，邊的權重w: E → ℝ。對於每個邊(u, v) ∈ E，w(u, v)表示從頂點u到頂點v的邊的權重。

單源最短路問題可以定義為：

給定圖G = (V, E)，邊權w，以及一個源點s ∈ V，找到從s到V中每個其他頂點t ∈ V的最短路徑。

所有對點最短路問題可以定義為：

給定圖G = (V, E)，邊權w，找到V中任意兩個頂點u, v ∈ V之間的最短路徑。

最短路問題在實際應用中非常常見，例如在交通網絡中找到從一個地點到另一個地點的最短路徑，或者在計算機網絡中找到數據包從一個路由器到另一個路由器的最短傳輸路徑。解決最短路問題的算法包括迪傑斯特拉算法（Dijkstra's algorithm）、弗洛伊德算法（Floyd's algorithm）和 Bellman-Ford算法等。這些算法可以有效地在給定的圖中找到最短路徑。