最大流量範例

最大流量問題（Maximum Flow Problem）是圖論中的一個經典問題，它的目標是在一個帶有權重的有向圖中，找到一條從源點（source）到匯點（sink）的最大流量路徑。這裡有一個簡單的例子來解釋最大流量問題：

假設我們有一個供應商A，它想要將一些產品運送到一個零售商B。中間有幾個中轉站C、D和E，每個中轉站都有自己的容量限制，並且可以接收和發貨。我們想要找到一條從A到B的路徑，使得總流量最大。

最大流量範例圖

在上圖中，供應商A是源點，零售商B是匯點。每條邊上的數字表示該邊的容量（流量限制）。例如，A到C的邊容量是20，C到D的邊容量是10，等等。

為了找到從A到B的最大流量路徑，我們可以使用福特-弗洛森算法（Ford-Fulkerson algorithm），這是一個貪心算法，它通過不斷地找到增廣路徑（augmenting path）來增加流。

  1. 初始時，所有邊的流量為0。
  2. 找到一條從源點A到匯點B的增廣路徑。增廣路徑是指一條不經過重複邊的有向路徑。
  3. 計算這條增廣路徑的 bottleneck capacity（最小邊容量）。
  4. 將這條增廣路徑上所有邊的流量增加 bottleneck capacity。
  5. 重複步驟2到步驟4，直到找不到增廣路徑為止。

在這個例子中，我們可以找到這樣一條增廣路徑：A -> C -> D -> B，其 bottleneck capacity 是10（因為C到D的邊容量是10）。我們將這條路徑上的所有邊的流量增加10，得到新的流量。然後我們再次尋找增廣路徑，這次我們找到的路徑是A -> C -> E -> B，其 bottleneck capacity 是15（因為C到E的邊容量是15）。我們再次將這條路徑上的所有邊的流量增加15。

重複這個過程，直到找不到增廣路徑為止。最後，我們得到的最大流量是45（因為A到C的邊容量是20，C到D的邊容量是10，D到B的邊容量是5，C到E的邊容量是15，E到B的邊容量是10，這些邊的流量加起來就是45）。

這個例子展示了如何使用福特-弗洛森算法來解決最大流量問題。當然，實際的應用可能會更加複雜，但是基本原理是相同的。