视频字幕
网络流问题是图论中的重要问题，研究如何在有向图中从源点传输最大流量到汇点。网络由节点和有向边组成，每条边都有容量限制。流必须满足两个基本约束：容量约束要求每条边的流量不超过其容量，流量守恒要求除了源点和汇点外，每个节点的流入量等于流出量。我们的目标是找到从源点到汇点的最大可能流量。
增广路径是Ford-Fulkerson算法的核心概念。首先我们需要构建残余网络：对于原网络中的每条边，如果还有剩余容量，就在残余网络中添加正向边；如果已有流量，就添加反向边允许流量回退。增广路径就是在残余网络中从源点到汇点的任意路径。找到增广路径后，我们可以沿着这条路径增加流量，从而改善当前的流。
Ford-Fulkerson算法是解决最大流问题的经典算法。算法从零流开始，重复寻找增广路径并沿路径增加流量。每次找到增广路径后，计算路径上的最小剩余容量，然后沿整条路径增加这个流量值。同时更新残余网络，继续寻找新的增广路径。当无法找到从源点到汇点的增广路径时，算法终止，此时得到的就是最大流。
Edmonds-Karp算法是Ford-Fulkerson算法的重要改进版本。关键优化在于使用广度优先搜索来选择增广路径，确保每次都选择边数最少的最短路径。这个看似简单的改变带来了重大的理论突破：将Ford-Fulkerson算法在最坏情况下的指数时间复杂度改进为多项式时间O(VE²)。通过BFS的系统性搜索，算法避免了可能的低效路径选择，保证了稳定的性能表现。