之前我们已经介绍了最大流问题的基本定义,让从源点流出的总流量达到最大,同时不违反任何管道的运输能力限制。学习了最大流最小割定理、增广路径与残量网络的构建方法,以及如何利用这些概念实现 EK 算法。EK 算法通过每次使用 BFS 寻找从源点到汇点的最短增广路径,保证了算法在有限步内终止,但是频繁的路径搜索会导致效率不高。
水往低处流:最大流的最高标号预留推进算法(HLPP)
未经允许不得转载:小狮博客 » 水往低处流:最大流的最高标号预留推进算法(HLPP)
之前我们已经介绍了最大流问题的基本定义,让从源点流出的总流量达到最大,同时不违反任何管道的运输能力限制。学习了最大流最小割定理、增广路径与残量网络的构建方法,以及如何利用这些概念实现 EK 算法。EK 算法通过每次使用 BFS 寻找从源点到汇点的最短增广路径,保证了算法在有限步内终止,但是频繁的路径搜索会导致效率不高。