编辑“︁网络流问题”︁（章节）

== 经典算法 ==  
=== Ford-Fulkerson 方法 ===  
通过不断寻找'''增广路径'''（augmenting path）来增加流量，直到无法继续。  

==== 伪代码 ====  
<syntaxhighlight lang="python">  
def ford_fulkerson(G, s, t):  
    max_flow = 0  
    residual_graph = initialize_residual_graph(G)  
    while exists_augmenting_path(residual_graph, s, t):  
        path = find_augmenting_path(residual_graph, s, t)  
        min_capacity = min_capacity_on_path(path)  
        max_flow += min_capacity  
        update_residual_graph(residual_graph, path, min_capacity)  
    return max_flow  
</syntaxhighlight>  

=== Edmonds-Karp 算法 ===  
Ford-Fulkerson 的改进版，使用 BFS 寻找最短增广路径，时间复杂度为 <math>O(VE^2)</math>。  

==== 示例 ====  
以下是一个网络流图及其最大流计算过程：  
<mermaid>  
graph LR  
    s -->|4/4| v1  
    s -->|2/2| v2  
    v1 -->|3/3| v3  
    v1 -->|1/1| v4  
    v2 -->|2/2| v4  
    v3 -->|3/3| t  
    v4 -->|3/3| t  
</mermaid>  
* 边上的标记表示流量/容量。  
* 最大流值为 5（4从s→v1→v3→t，1从s→v1→v4→t）。