最小费用流的残留图算法详解：求解最短路径与费用优化

最小费用流的残留图是解决最小费用流问题的关键概念，它是在网络流分析中用来辅助理解流量分配过程的一种工具。在网络流模型中，我们考虑一个有向图G，其中包含一个源点s和一个汇点t，以及定义在边集上的容量函数c和费用函数w。最小费用流问题的目标是找到从s到t的流f，使得总流量满足特定要求，同时这个流的总费用w(e) * f(e)尽可能小。 网络流问题通常涉及两个主要性质：容量限制（每个边都有一个最大流的上限）和流守恒性（流入节点的流量等于流出节点的流量）。最大流问题是最基本的形式，而最小费用流则在此基础上增加了成本优化的约束。 残留图是处理这个问题的有效手段。在残留图中，每条边的剩余容量c'(e) = c(e) - f(e)和残余费用w'(e) = w(e) - f(e)被用来表示原有网络流的剩余可能性。通过计算残留图，我们可以找到从s到t的最短增广路，即在不违反容量限制的前提下，能够增加流量的最短路径。 在给出的示例中，有几条边具有不同的容量c(e)和费用w(e)。例如，边①到⑦的容量为5，费用为4；边①到④的容量为6，费用为3。在初始状态下，f(e) = 2，因此残留容量和费用分别为c'(e)和w'(e)。通过寻找最短增广路并逐步增加流值，可以找到满足流量要求且总费用最小的解。 最小费用流算法如最小费用路算法（Successive Shortest Path Algorithm）就是基于这个原理设计的。该算法从零流开始，每次找到一条费用最小的增广路径，直到无法再增加流为止。这种算法的时间复杂度为O(n^2C)，其中n是顶点数，C是每条边的增广次数。在实际应用中，由于采用了最短路径算法，它在寻找增广路径上比直接遍历所有可能的路径更有效率。 在示例中，第一次增广路径选择了边①—③—⑤—⑦，增加了3单位流量；第二次增广路径则选择了边①—④—⑥—⑦，增加了5单位流量。每一步都确保了费用的最小化，直到达到无增广路径的状态，即达到最小费用流的解。通过残留图和增广路径分析，我们可以得到一个既满足流量需求又具有最低总费用的网络流方案。