每日算法 — 使用java实现费用流：最小费用流与SPFA消圈算法

引言

在网络流问题中，我们不仅关心从源点到汇点能输送多少流量，还常常需要考虑输送这些流量的成本。例如物流配送中不同路线的运输费用、通信网络中不同链路的带宽成本、任务调度中不同工人完成任务的报酬差异等场景，都需要在流量约束下最小化总成本。最小费用流问题（Minimum Cost Flow）正是为此而设计的经典网络优化模型。

与最大流问题只求流量最大化不同，最小费用流问题在每条边上同时定义容量和费用，目标是找到满足指定流量的可行流，使得总费用最小。该问题是线性规划的特例，可以通过网络单纯形法或基于最短路径的增广算法高效求解。

核心原理

问题定义

给定一个有向图 G=(V, E)，每条边 e 具有：
– 容量 c(e) ≥ 0：边上能通过的最大流量
– 费用 w(e)：边上每单位流量的运输成本

指定源点 s、汇点 t 和目标流量 F，求一个从 s 到 t 的流量为 F 的可行流，使得总费用最小。

残量网络与费用

与最大流类似，费用流也使用残量网络：
– 对于原边 (u, v)，残量容量为 c(u,v) - f(u,v)，残量费用为 w(u,v)
– 对于反向边 (v, u)，残量容量为 f(u,v)，残量费用为 -w(u,v)

反向边的负费用允许算法”撤销”之前的选择，这是费用流算法能找到最优解的关键。

消圈定理

定理：一个可行流是最小费用流，当且仅当残量网络中不存在负费用增广圈。

基于该定理，算法设计有两条主线：
1. 连续最短路算法（SSP, Successive Shortest Path）：每次在残量网络中找从s到t的最短费用路径进行增广
2. 消圈算法（Cycle Canceling）：先找任意可行流，然后在残量网络中不断找负圈并沿其增广消去

本文实现SSP算法，因其在实际中效率更高且更容易实现。

SPFA算法求最短路

在费用流的残量网络中，边权（费用）可能为负，但不存在负圈（因为每次沿最短路增广后，残量网络中的距离势保证了无负圈）。因此可以使用SPFA（Shortest Path Faster Algorithm）来求最短路，它比Bellman-Ford更快，且能处理负权边。

Java实现

核心数据结构

import java.util.*;

/**
 * 最小费用流实现
 * 基于连续最短路算法（Successive Shortest Path）
 * 使用SPFA求残量网络中的最短路
 */
public class MinCostFlow {

    /**
     * 边类：同时支持正向边和反向边
     */
    static class Edge {
        int to;          // 目标节点
        int rev;         // 反向边在目标节点邻接表中的索引
        int capacity;    // 残量容量
        int cost;        // 单位费用
        int originalCap; // 原始容量（用于调试）

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

    private int n;                      // 节点数
    private List<Edge>[] graph;         // 邻接表
    private int[] dist;                 // 最短距离
    private int[] parentV;              // 最短路径上的父节点
    private int[] parentE;              // 最短路径上的父边索引
    private boolean[] inQueue;          // SPFA标记
    private static final int INF = Integer.MAX_VALUE / 2;

    @SuppressWarnings("unchecked")
    public MinCostFlow(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        this.dist = new int[n];
        this.parentV = new int[n];
        this.parentE = new int[n];
        this.inQueue = new boolean[n];
    }

    /**
     * 添加一条带费用的边
     * @param from 起点
     * @param to 终点
     * @param capacity 容量
     * @param cost 单位费用
     */
    public void addEdge(int from, int to, int capacity, int cost) {
        Edge forward = new Edge(to, graph[to].size(), capacity, cost);
        Edge backward = new Edge(from, graph[from].size(), 0, -cost);
        graph[from].add(forward);
        graph[to].add(backward);
    }

    /**
     * SPFA求最短路（可处理负权边）
     * @param source 源点
     * @param sink 汇点
     * @return 是否存在从source到sink的路径
     */
    private boolean spfa(int source, int sink) {
        Arrays.fill(dist, INF);
        Arrays.fill(inQueue, false);
        dist[source] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        inQueue[source] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (int i = 0; i < graph[u].size(); i++) {
                Edge e = graph[u].get(i);
                if (e.capacity > 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]) {
                        queue.offer(e.to);
                        inQueue[e.to] = true;
                    }
                }
            }
        }

        return dist[sink] < INF;
    }

    /**
     * 求解最小费用流
     * @param source 源点
     * @param sink 汇点
     * @param maxFlow 需要输送的最大流量
     * @return [实际输送流量, 总费用]，如果无法输送maxFlow则返回实际能输送的最大流量及对应费用
     */
    public int[] minCostMaxFlow(int source, int sink, int maxFlow) {
        int flow = 0;
        int cost = 0;

        while (flow < maxFlow && spfa(source, sink)) {
            // 计算当前最短路径上的可增广流量
            int addFlow = maxFlow - flow;
            int v = sink;
            while (v != source) {
                int u = parentV[v];
                Edge e = graph[u].get(parentE[v]);
                addFlow = Math.min(addFlow, e.capacity);
                v = u;
            }

            // 增广
            v = sink;
            while (v != source) {
                int u = parentV[v];
                Edge e = graph[u].get(parentE[v]);
                Edge rev = graph[v].get(e.rev);
                e.capacity -= addFlow;
                rev.capacity += addFlow;
                v = u;
            }

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

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

    /**
     * 获取当前某条边上的实际流量
     * 通过原始容量减去残量容量得到
     */
    public int getFlow(int from, int edgeIdx) {
        Edge e = graph[from].get(edgeIdx);
        return e.originalCap - e.capacity;
    }

    /**
     * 打印当前网络状态（调试用）
     */
    public void printNetwork() {
        System.out.println("Network State:");
        for (int u = 0; u < n; u++) {
            for (int i = 0; i < graph[u].size(); i++) {
                Edge e = graph[u].get(i);
                if (e.originalCap > 0) { // 只打印原始边
                    int flow = e.originalCap - e.capacity;
                    System.out.printf("  Edge %d -> %d: flow=%d/%d cost=%d%n", 
                        u, e.to, flow, e.originalCap, e.cost);
                }
            }
        }
    }
}

消圈算法实现

/**
 * 费用流的消圈算法实现
 * 先通过最大流找可行流，再在残量网络中不断消去负圈
 */
public class CycleCanceling {

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

    private int n;
    private List<Edge>[] graph;
    private static final int INF = Integer.MAX_VALUE / 2;

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

    public void addEdge(int from, int to, int capacity, int cost) {
        Edge f = new Edge(to, graph[to].size(), capacity, cost);
        Edge b = new Edge(from, graph[from].size(), 0, -cost);
        graph[from].add(f);
        graph[to].add(b);
    }

    /**
     * 使用SPFA找负圈，返回负圈上的节点列表
     */
    private List<Integer> findNegativeCycle() {
        int[] dist = new int[n];
        int[] parentV = new int[n];
        int[] parentE = new int[n];
        int[] count = new int[n];
        boolean[] inQueue = new boolean[n];

        Arrays.fill(dist, 0); // 初始化为0，更容易找到负圈
        Arrays.fill(parentV, -1);

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i);
            inQueue[i] = true;
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (int i = 0; i < graph[u].size(); i++) {
                Edge e = graph[u].get(i);
                if (e.capacity > 0 && dist[u] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[u] + e.cost;
                    parentV[e.to] = u;
                    parentE[e.to] = i;
                    count[e.to] = count[u] + 1;

                    if (count[e.to] >= n) {
                        // 找到负圈，回溯获取圈上的节点
                        boolean[] visited = new boolean[n];
                        int cur = e.to;
                        while (!visited[cur]) {
                            visited[cur] = true;
                            cur = parentV[cur];
                        }

                        List<Integer> cycle = new ArrayList<>();
                        int start = cur;
                        do {
                            cycle.add(cur);
                            cur = parentV[cur];
                        } while (cur != start);
                        Collections.reverse(cycle);
                        return cycle;
                    }

                    if (!inQueue[e.to]) {
                        queue.offer(e.to);
                        inQueue[e.to] = true;
                    }
                }
            }
        }

        return null; // 无负圈
    }

    /**
     * 沿负圈增广
     */
    private int augmentAlongCycle(List<Integer> cycle) {
        int minFlow = INF;
        int m = cycle.size();

        // 找圈上的最小残量
        for (int i = 0; i < m; i++) {
            int u = cycle.get(i);
            int v = cycle.get((i + 1) % m);
            for (Edge e : graph[u]) {
                if (e.to == v && e.capacity > 0) {
                    minFlow = Math.min(minFlow, e.capacity);
                    break;
                }
            }
        }

        // 增广
        for (int i = 0; i < m; i++) {
            int u = cycle.get(i);
            int v = cycle.get((i + 1) % m);
            for (int j = 0; j < graph[u].size(); j++) {
                Edge e = graph[u].get(j);
                if (e.to == v && e.capacity > 0) {
                    e.capacity -= minFlow;
                    graph[v].get(e.rev).capacity += minFlow;
                    break;
                }
            }
        }

        return minFlow;
    }

    /**
     * 消圈算法求解最小费用流
     * 注意：此实现需要先确保可行流存在
     */
    public int[] solve(int source, int sink, int requiredFlow) {
        // 第一步：通过最大流算法找可行流（简化版：直接用SSP找）
        // 这里为了展示消圈思想，先假设可行流已通过其他方式找到
        // 实际使用时，可以先跑一遍最大流确保流量足够

        int iterations = 0;
        while (iterations < 10000) {
            List<Integer> cycle = findNegativeCycle();
            if (cycle == null) break;
            augmentAlongCycle(cycle);
            iterations++;
        }

        // 计算总流量和总费用
        int flow = 0, cost = 0;
        for (int u = 0; u < n; u++) {
            for (Edge e : graph[u]) {
                if (e.originalCap > 0) {
                    int f = e.originalCap - e.capacity;
                    cost += f * e.cost;
                }
            }
        }
        // 费用被正向和反向边各算了一次，除以2
        cost /= 2;

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

测试用例

public class MinCostFlowDemo {
    public static void main(String[] args) {
        // 案例：从仓库(0)向三个商店(1,2,3)配送货物
        // 节点4是虚拟汇点，收集所有商店的流量
        System.out.println("=== 最小费用流案例 ===");

        int n = 5;
        MinCostFlow mcf = new MinCostFlow(n);

        // 仓库到各商店的配送路线（容量，单位费用）
        mcf.addEdge(0, 1, 10, 4);  // 路线0->1：容量10，费用4
        mcf.addEdge(0, 2, 8, 3);   // 路线0->2：容量8，费用3
        mcf.addEdge(0, 3, 12, 6);  // 路线0->3：容量12，费用6

        // 商店到汇点
        mcf.addEdge(1, 4, 10, 0);
        mcf.addEdge(2, 4, 8, 0);
        mcf.addEdge(3, 4, 12, 0);

        // 额外路线：商店之间的中转
        mcf.addEdge(1, 2, 5, 1);   // 1->2中转，费用1
        mcf.addEdge(2, 3, 6, 2);   // 2->3中转，费用2

        int source = 0, sink = 4;
        int requiredFlow = 15;

        int[] result = mcf.minCostMaxFlow(source, sink, requiredFlow);
        System.out.println("请求流量: " + requiredFlow);
        System.out.println("实际流量: " + result[0]);
        System.out.println("总费用: " + result[1]);

        mcf.printNetwork();

        // 案例2：最小费用最大流
        System.out.println("\n=== 最小费用最大流案例 ===");
        MinCostFlow mcf2 = new MinCostFlow(4);
        mcf2.addEdge(0, 1, 3, 1);
        mcf2.addEdge(0, 2, 2, 2);
        mcf2.addEdge(1, 2, 2, 1);
        mcf2.addEdge(1, 3, 3, 3);
        mcf2.addEdge(2, 3, 4, 1);

        int[] result2 = mcf2.minCostMaxFlow(0, 3, Integer.MAX_VALUE);
        System.out.println("最大流: " + result2[0]);
        System.out.println("最小费用: " + result2[1]);

        mcf2.printNetwork();
    }
}

复杂度分析

其中 F 为流量，V 为顶点数，E 为边数，C 为最大费用。使用势函数（Johnson技巧）将边权转换为非负后，可以用Dijkstra替代SPFA，将每次最短路的复杂度从O(VE)降至O(E log V)。

势函数优化

/**
 * 使用势函数的Dijkstra优化版本
 * 通过维护势函数h，将边权转化为非负值
 */
public int[] minCostMaxFlowWithPotential(int source, int sink, int maxFlow) {
    int[] potential = new int[n]; // 势函数
    int flow = 0, cost = 0;

    while (flow < maxFlow) {
        // Dijkstra求最短路（边权已非负）
        Arrays.fill(dist, INF);
        dist[source] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0];
            if (cur[1] > dist[u]) continue;

            for (int i = 0; i < graph[u].size(); i++) {
                Edge e = graph[u].get(i);
                if (e.capacity > 0) {
                    // 约化费用 = 原费用 + h[u] - h[v]
                    int reducedCost = e.cost + potential[u] - potential[e.to];
                    if (dist[u] + reducedCost < dist[e.to]) {
                        dist[e.to] = dist[u] + reducedCost;
                        parentV[e.to] = u;
                        parentE[e.to] = i;
                        pq.offer(new int[]{e.to, dist[e.to]});
                    }
                }
            }
        }

        if (dist[sink] == INF) break;

        // 更新势函数
        for (int i = 0; i < n; i++) {
            if (dist[i] < INF) potential[i] += dist[i];
        }

        // 增广（使用原始费用计算）
        int addFlow = maxFlow - flow;
        int v = sink;
        while (v != source) {
            int u = parentV[v];
            Edge e = graph[u].get(parentE[v]);
            addFlow = Math.min(addFlow, e.capacity);
            v = u;
        }

        v = sink;
        while (v != source) {
            int u = parentV[v];
            Edge e = graph[u].get(parentE[v]);
            Edge rev = graph[v].get(e.rev);
            e.capacity -= addFlow;
            rev.capacity += addFlow;
            v = u;
        }

        flow += addFlow;
        cost += addFlow * potential[sink]; // 势函数累积了原始最短路长度
    }

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

应用场景

1. 物流调度：最小化运输成本的同时满足配送需求
2. 任务分配：将任务分配给工人，使总报酬最小
3. 网络路由：在带宽约束下选择成本最低的数据传输路径
4. 生产计划：在产能约束下最小化生产成本
5. 图像分割：基于图割的费用流模型进行图像前景背景分离

总结

最小费用流问题通过引入费用维度，将网络流从单纯的流量最大化扩展为成本优化模型。本文实现了基于SPFA的连续最短路算法，并展示了消圈算法的核心思想。理解费用流的关键在于掌握残量网络中的反向边机制和消圈定理，这些是保证算法最优性的理论基础。