← 回入口

網路流 (Network Flow)

圖論中的流量優化問題

基礎概念

網路流問題研究如何在有容量限制的網路中，從源點到匯點傳輸最大流量。典型應用包括交通網路、資料傳輸、通訊網路、航空公司調度。

Ford-Fulkerson 演算法

核心思想：在剩餘網路中反覆尋找增廣路徑，增加流量，直到沒有增廣路徑為止。時間複雜度 O(E × maxflow)。

def ford_fulkerson(graph, source, sink): flow = 0 while path := bfs_find_path(graph, source, sink): bottleneck = min(cap for (_, _, cap) in path) for u, v, _ in path: graph[u][v] -= bottleneck graph[v][u] += bottleneck flow += bottleneck return flow

最大流最小割定理

在任何網路中，從源點到匯點的最大流量值等於最小割的容量。這個優美的對偶性是網路流理論的核心，也是許多演算法正確性的基礎。

應用場景

二分圖最大匹配、運輸問題、工作分配、影像分割（Graph Cut）、通訊網路可靠度分析。

本課程範例

相關連結