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

问题引入

在网络流问题中，最大流仅关注流量大小，而实际应用中往往每条边还有运输成本。最小费用最大流要求在满足最大流的前提下，总运输费用最小。该模型广泛应用于物流调度、任务分配、网络路由等场景。本文用Java实现基于SPFA（Shortest Path Faster Algorithm）的最小费用最大流算法，采用连续最短路增广策略，每次沿费用最短的增广路推送流量。

算法原理

残量网络与费用流

费用流在普通网络流基础上，为每条边增加一个单位流量费用cost。构造残量网络时，正向边剩余容量为cap - flow，反向边容量为flow，反向边的费用为正向边费用的相反数。这样允许算法在后续步骤中”撤销”之前不优的流量分配。

连续最短路增广

每次在残量网络上用SPFA寻找从源点到汇点的最短费用路径（按费用而非距离），然后沿该路径尽可能增广。重复此过程直到不存在增广路。由于每次沿最短路增广，该策略能保证最终流的总费用最小。

SPFA优化

SPFA是Bellman-Ford的队列优化版本，利用SLF（Small Label First）策略将节点入队时插入队首而非队尾，对于稀疏图有显著加速效果。在费用流场景中，图通常较稀疏，SPFA表现优异。

完整Java实现

package algorithm.mcmf;

import java.util.*;

/**
 * 最小费用最大流（MCMF）
 * 基于SPFA连续最短路增广
 */
public class MinCostMaxFlow {

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

    private final int n;
    private final List<List<Edge>> graph;
    private final long INF = Long.MAX_VALUE / 4;

    public MinCostMaxFlow(int n) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
    }

    /**
     * 添加带费用的有向边
     * @param from 起点
     * @param to 终点
     * @param cap 容量
     * @param cost 单位流量费用
     */
    public void addEdge(int from, int to, int cap, long cost) {
        Edge forward = new Edge(to, graph.get(to).size(), cap, cost);
        Edge backward = new Edge(from, graph.get(from).size(), 0, -cost);
        graph.get(from).add(forward);
        graph.get(to).add(backward);
    }

    /**
     * 计算从s到t的最小费用最大流
     * @param s 源点
     * @param t 汇点
     * @return [最大流, 最小费用]
     */
    public long[] minCostMaxFlow(int s, int t) {
        long flow = 0, cost = 0;
        long[] dist = new long[n];
        int[] parentV = new int[n]; // 父节点顶点
        int[] parentE = new int[n]; // 父节点边索引

        while (true) {
            // SPFA找最短路
            Arrays.fill(dist, INF);
            boolean[] inQueue = new boolean[n];
            dist[s] = 0;
            Deque<Integer> queue = new ArrayDeque<>();
            queue.offer(s);
            inQueue[s] = true;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                inQueue[u] = false;
                List<Edge> edges = graph.get(u);
                for (int i = 0; i < edges.size(); i++) {
                    Edge e = edges.get(i);
                    if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        parentV[e.to] = u;
                        parentE[e.to] = i;
                        if (!inQueue[e.to]) {
                            // SLF优化：距离更小则放队首
                            if (!queue.isEmpty() && dist[e.to] < dist[queue.peek()]) {
                                queue.offerFirst(e.to);
                            } else {
                                queue.offerLast(e.to);
                            }
                            inQueue[e.to] = true;
                        }
                    }
                }
            }

            if (dist[t] == INF) break; // 不存在增广路

            // 计算增广量
            int addFlow = Integer.MAX_VALUE;
            for (int v = t; v != s; v = parentV[v]) {
                Edge e = graph.get(parentV[v]).get(parentE[v]);
                addFlow = Math.min(addFlow, e.cap);
            }

            // 增广并更新费用
            for (int v = t; v != s; v = parentV[v]) {
                Edge e = graph.get(parentV[v]).get(parentE[v]);
                e.cap -= addFlow;
                graph.get(v).get(e.rev).cap += addFlow;
            }

            flow += addFlow;
            cost += addFlow * dist[t];
        }

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

    /**
     * 获取当前某条边的实际流量（通过反向边容量获取）
     */
    public int getFlow(int from, int edgeIndex) {
        Edge e = graph.get(from).get(edgeIndex);
        return graph.get(e.to).get(e.rev).cap;
    }

    public static void main(String[] args) {
        // 示例1：经典运输问题
        // 工厂(0) -> 仓库(1,2) -> 客户(3,4) -> 汇点(5)
        MinCostMaxFlow mcmf = new MinCostMaxFlow(6);
        mcmf.addEdge(0, 1, 10, 2);  // 工厂到仓库1，容量10，费用2
        mcmf.addEdge(0, 2, 10, 3);  // 工厂到仓库2，容量10，费用3
        mcmf.addEdge(1, 3, 5, 1);   // 仓库1到客户1
        mcmf.addEdge(1, 4, 5, 4);   // 仓库1到客户2
        mcmf.addEdge(2, 3, 5, 3);   // 仓库2到客户1
        mcmf.addEdge(2, 4, 5, 1);   // 仓库2到客户2
        mcmf.addEdge(3, 5, 10, 0);  // 客户1到汇点
        mcmf.addEdge(4, 5, 10, 0);  // 客户2到汇点

        long[] result = mcmf.minCostMaxFlow(0, 5);
        System.out.printf("最大流: %d, 最小费用: %d%n", result[0], result[1]);

        // 示例2：任务分配问题（二分图最小权匹配）
        // 3个工人，3个任务，求最小成本分配
        MinCostMaxFlow assign = new MinCostMaxFlow(8);
        int source = 0, sink = 7;
        for (int worker = 1; worker <= 3; worker++) {
            assign.addEdge(source, worker, 1, 0);
        }
        for (int task = 4; task <= 6; task++) {
            assign.addEdge(task, sink, 1, 0);
        }
        // 成本矩阵
        long[][] costs = {{3, 2, 4}, {1, 5, 2}, {4, 3, 1}};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                assign.addEdge(i + 1, j + 4, 1, costs[i][j]);
            }
        }
        long[] assignResult = assign.minCostMaxFlow(source, sink);
        System.out.printf("任务分配最大流: %d, 最小总成本: %d%n", assignResult[0], assignResult[1]);
    }
}

复杂度分析

对于单位容量图（如任务分配），maxFlow不超过V，复杂度退化为O(V^2 * E)。若图中存在负权边但无负权环，SPFA依然适用。对于大规模图，可考虑用Dijkstra+势能函数（Johnson算法思想）将复杂度优化到O(maxFlow * E * logV)。

关键技巧总结

• 反向边费用设为正向边费用的相反数，是实现流量”撤销”的关键
• SLF优化（Small Label First）将距离更小的节点插入队首，可加速SPFA收敛
• getFlow 通过读取反向边容量来获取实际流量，这是残量网络的特性
• 连续最短路策略要求费用非负或不存在负权环，否则需要用消圈算法