图论中求解网络最大流问题有哪些经典算法，近年又提出了哪些改进方法？

经典算法

Ford-Fulkerson方法：通过不断寻找增广路径增加流量，直至无增广路。时间复杂度依赖容量值，整数容量下为O(E·f_max)。

Edmonds-Karp算法：Ford-Fulkerson的特例，强制使用BFS寻找最短增广路，将复杂度优化至O(V·E²)。

Dinic算法：引入分层图与阻塞流概念，每阶段构建层次网络并多路增广，复杂度为O(V²·E)，在单位容量网络中可达O(E·√V)。

Push-Relabel（预流推进）算法：不沿完整路径增广，而是对节点维护超额流并推送或抬升高度，最高标号实现复杂度为O(V²·√E)。

近年改进方法

基于电网络的近似算法：将最大流转化为拉普拉斯线性系统求解，利用内点法与图稀疏化技术，在稠密图上逼近近乎线性的时间复杂度。

动态最大流算法：针对边权或拓扑频繁变化的场景，采用增量更新策略避免全量重算，适用于实时网络路由调整。

并行与分布式计算：利用GPU多线程或MapReduce框架加速阻塞流计算，处理超大规模网络。

机器学习辅助：用图神经网络预测增广路径优先级或初始预流分布，减少搜索空间。

适用条件与选择依据

• 稀疏图且容量较小：Edmonds-Karp实现简单，适合小规模。
• 一般网络：Dinic算法综合性能优异，是竞赛与工程常用选择。
• 稠密图或需严格理论界：Push-Relabel更优。
• 超大规模近似求解：考虑基于拉普拉斯系统的近线性算法。

常见误区

• Ford-Fulkerson是无理数容量时可能不终止或收敛到错误值，并非所有实现都保证正确性。
• Dinic算法的实际运行速度常远优于其最坏复杂度上界，不应仅凭理论复杂度否定其工程价值。
• 近似算法给出的是(1+ε)近似解，不适用于要求精确整数流的场景。