什么是最大流問題

最大流問題（Maximum Flow Problem）是圖論中的一個經典問題，它的目標是在一個帶有權重的有向圖（通常稱為流圖）中，找到一條從源點（source）到匯點（sink）的最大流量路徑。這裡的「流量」可以理解為某種資源在圖中流動的數量，例如在電力網絡中可以代表電流，在物流網絡中可以代表貨物量。

最大流問題的定義如下：

給定一個有向圖G = (V, E)，其中V是頂點集合，E是邊集合。圖中有一個特定的源點s ∈ V 和一個特定的匯點t ∈ V。每條邊(u, v) ∈ E都有一個非負的容量（capacity）c(u, v)，表示從頂點u到頂點v的最大流量。

問題的目標是在不違反邊的容量的前提下，找到從源點s到匯點t的最大流量，同時最大化從s到t的流量。這個問題通常可以用福特-福克森算法（Ford-Fulkerson algorithm）或Edmonds-Karp算法來解決，它們都是動態規劃算法，可以找到圖中的最大流。