Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(2)
最大流问题的应用主要表现在下面几个方面：
（1）在许多现实的网络中需要确定在两点之间最大可输送的流量；
（2）许多问题表面上看起来和最大流问题无关，但其实它们可以通过图论和线性规划等方法把问题转化为最大流问题；
（3）最大流问题常常作为一些其他的问题，主要是图论、组合优化和线性规划等问题的子问题出现。
最大流问题已经有多年的研究历史，而它的应用也一直是十分有意义的研究工作。网络流问题的研究者和具体问题的工程师从各个不同的角度充实着这方面的研究。无论是从线性规划还是组合优化的角度来看，最大流问题都是一个已经被研究得比较深入的问题，该领域已经存在许多优秀的算法和大量优秀的代码。因此，把许多问题转化为最大流问题或最小割问题后可以得到十分有效地解决。而发现具体的问题与最大流或最小割问题之间的联系是其应用的关键，这对各种应用问题的研究更是至关重要的。
1.2 国内外研究现状与发展趋势
最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者Hitchcock，1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型。后来Koopmans在1947年独立地提出运输问题并详细地对此问题加以讨论。1955年 ，T.E.Harris在研究铁路最大通行量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. Ford和 D.R. Fulkerson等人给出了解决这类问题的算法，从而建立了网络流理论。
从上世纪50年代提出以来，最大流问题的研究已有优尔十多年的历史，科学家们开发了大量求解最大流问题的算法。最早的算法是Dantzig在1951年提出的网络单纯形法以及Ford与Fulkerson在1956年提出的增广路算法（即著名的Ford–Fulkerson算法[1]），但它们都是伪多项式时间的算法。20世纪70年代开始出现了多项式时间的算法，分别由Dinic，Edmonds和Karp等提出的在分层网络的增广路上增广的方法[4]。1973年，Dinic首次获得了时间复杂度的核心因子为 的算法。虽然以后的几十年中，最大流算法获得了很大的进展，许多优秀的算法不断被提出，但是算法时间复杂度的进步一直都停留在对对数因子的改进上，而 的时间复杂度核心因子始终没有被突破。直到1998年，Goldberg和Rao的文献《Beyond the flow decomposition barrier》出现，算法的时间复杂度才突破 的核心因子。
在最大流问题中， 时间界是一个自然的障碍。如果我们把一个流沿从源点到收点的各个路径进行分解，根据流分解定理，这些包含流的路径的总长度为 。因此，对每次利用一条增广路的算法， 时间复杂度是这类算法的下界。尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的，但在很长一段时间内， 的时间界没有被突破。 时间被称为最大流问题的流分解障碍。
通过根据剩余流量对网络中的边赋予长度，并把由剩余容量较大的边构成的强连通分量收缩成一点等方法，1998年，Goldberg和Rao首次获得了整数容量网络中的一个突破流分解障碍的算法——二分长度阻塞流算法。该算法的时间复杂度为 ，使最大流问题算法时间复杂度的核心因子由 降为 。该算法包含了大量的网络变换的操作，因此算法很复杂，实现起来比较困难。
到1998年为止，对一般的实数容量的最大流问题，最好的通用算法的时间复杂度为 ；而对整数容量的问题，最好的算法的时间复杂度为 。
尽管最大流问题已有超过优尔十年的研究历史，但到目前为止，人们还没有发现该问题的精确下界，更没有发现达到问题下界的算法。因此改进最大流算法的时间复杂度仍是一个十分重要的研究课题。另外，开发解决具有特殊结构的网络的算法将是最大流算法研究的重要趋势之一。[9]