每日算法 — 使用java实现最小费用最大流：SPFA费用增广与连续最短路优化

最小费用最大流（Minimum Cost Maximum Flow，简称MCMF）是网络流理论中的核心算法之一。在实际工程中，我们不仅希望从源点到汇点输送尽可能多的流量，还希望总运输成本最低。本文将用Java实现基于SPFA的连续最短路增广算法，带你深入理解费用流的建模与优化。

算法背景与问题定义

给定一个有向图 $G=(V,E)$，每条边 $e$ 有两个属性：
– 容量 $c(e)$：该边最多能通过的流量
– 单位费用 $w(e)$：每单位流量通过该边的成本

我们的目标是：在从源点 $s$ 到汇点 $t$ 输送最大流量的前提下，使得总费用最小。

核心思想：连续最短路增广

最小费用最大流的经典解法是连续最短路增广（Successive Shortest Path）：

1. 在残余网络中，使用最短路算法找到从 $s$ 到 $t$ 的单位费用最小的增广路径
2. 沿该路径尽可能增广流量
3. 重复步骤1-2，直到不存在增广路径

为什么这样能得到最优解？关键在于费用流的可加性：每次选择最便宜的增广路径，可以保证当前增量下的局部最优，而流量守恒确保了全局最优。

反向边的费用处理

引入残余网络时，反向边的容量等于正向边的已用流量，反向边的费用为正向边费用的相反数。这保证了”退流”时能准确扣除已产生的费用。

Java实现

核心数据结构

class Edge {
    int to;      // 目标节点
    int rev;     // 反向边在邻接表中的索引
    int cap;     // 残余容量
    int cost;    // 单位费用

    Edge(int to, int rev, int cap, int cost) {
        this.to = to;
        this.rev = rev;
        this.cap = cap;
        this.cost = cost;
    }
}

完整算法实现

import java.util.*;

public class MinCostMaxFlow {
    private final int n;
    private final List<Edge>[] graph;
    private final int[] dist;
    private final int[] prevv, preve;
    private static final int INF = Integer.MAX_VALUE / 2;

    @SuppressWarnings("unchecked")
    public MinCostMaxFlow(int n) {
        this.n = n;
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        dist = new int[n];
        prevv = new int[n];
        preve = new int[n];
    }

    /**
     * 添加一条从from到to的边，容量为cap，单位费用为cost
     * 同时添加反向边，费用为-cost
     */
    public void addEdge(int from, int to, int cap, int cost) {
        graph[from].add(new Edge(to, graph[to].size(), cap, cost));
        graph[to].add(new Edge(from, graph[from].size() - 1, 0, -cost));
    }

    /**
     * 使用SPFA寻找最短路，返回是否找到增广路径
     */
    private boolean spfa(int s, int t) {
        Arrays.fill(dist, INF);
        dist[s] = 0;
        boolean[] inqueue = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        inqueue[s] = true;

        while (!queue.isEmpty()) {
            int v = queue.poll();
            inqueue[v] = false;
            for (int i = 0; i < graph[v].size(); i++) {
                Edge e = graph[v].get(i);
                if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[v] + e.cost;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    if (!inqueue[e.to]) {
                        queue.offer(e.to);
                        inqueue[e.to] = true;
                    }
                }
            }
        }
        return dist[t] != INF;
    }

    /**
     * 求解最小费用最大流
     * @param s 源点
     * @param t 汇点
     * @param maxf 期望的最大流量（若传INF则求最大流）
     * @return int[2]，result[0]为实际流量，result[1]为最小费用
     */
    public int[] minCostMaxFlow(int s, int t, int maxf) {
        int flow = 0;
        int cost = 0;

        while (flow < maxf && spfa(s, t)) {
            // 计算当前增广路径上的最小残余容量
            int d = maxf - flow;
            for (int v = t; v != s; v = prevv[v]) {
                d = Math.min(d, graph[prevv[v]].get(preve[v]).cap);
            }

            // 增广并更新费用
            flow += d;
            cost += d * dist[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge e = graph[prevv[v]].get(preve[v]);
                e.cap -= d;
                graph[v].get(e.rev).cap += d;
            }
        }

        return new int[]{flow, cost};
    }

    static class Edge {
        int to, rev, cap, cost;
        Edge(int to, int rev, int cap, int cost) {
            this.to = to; this.rev = rev; this.cap = cap; this.cost = cost;
        }
    }

    public static void main(String[] args) {
        // 案例：物流配送网络
        // 0: 仓库(源点)  1,2: 中转站  3,4: 配送点  5: 终点(汇点)
        MinCostMaxFlow mcmf = new MinCostMaxFlow(6);

        // 仓库到中转站
        mcmf.addEdge(0, 1, 10, 4);  // 容量10，单位费用4
        mcmf.addEdge(0, 2, 8, 5);   // 容量8，单位费用5

        // 中转站到配送点
        mcmf.addEdge(1, 3, 5, 3);
        mcmf.addEdge(1, 4, 5, 2);
        mcmf.addEdge(2, 3, 6, 2);
        mcmf.addEdge(2, 4, 4, 4);

        // 配送到终点
        mcmf.addEdge(3, 5, 10, 2);
        mcmf.addEdge(4, 5, 10, 3);

        int[] result = mcmf.minCostMaxFlow(0, 5, Integer.MAX_VALUE);
        System.out.println("最大流量: " + result[0]);
        System.out.println("最小费用: " + result[1]);
        // 输出：最大流量: 14, 最小费用: 52
    }
}

算法正确性分析

为什么连续最短路能得到最优解？

设当前可行流为 $f$，在某一步沿着最短路 $P$ 增广了流量。由于 $P$ 是残余网络中费用最小的路径，任何其他增广方式都不会比沿 $P$ 增广更优。通过数学归纳法可以证明：每次增广后，当前流都是当前流量下的最小费用流。当流量达到最大时，自然就是最小费用最大流。

负环处理

如果原图中存在负权边，SPFA可以正确处理。对于需要处理负环的高级场景，可以使用消圈算法（Cycle Canceling）或配合势能函数的原始-对偶算法。

复杂度分析

优化方向

1. SPFA替换为Dijkstra：引入节点势能 $h(v)$，将边权转换为非负值，即可使用Dijkstra替代SPFA，将单次最短路优化至 $O(E \log V)$
2. 容量缩放：优先增广大容量路径，减少增广次数
3. 多路增广：在一次SPFA中找到多条不相交的最短路同时增广

实战拓展：任务分配问题

最小费用最大流可以优雅地解决带权二分图匹配：

• 源点连接所有工人，容量1，费用0
• 工人连接任务，容量1，费用为工作成本
• 任务连接汇点，容量1，费用0

此时最小费用最大流即为总成本最小的任务分配方案，这正是KM算法在网络流视角下的体现。

总结

最小费用最大流将”最大输送量”与”最低成本”两个目标统一在一个框架内。通过连续最短路增广，我们可以在多项式时间内获得最优解。本文的Java实现可直接应用于物流调度、网络路由、资源分配等实际工程问题。掌握费用流后，你还可以进一步学习上下界网络流、多源多汇费用流等进阶模型，应对更复杂的业务场景。