How would you implement minimum-cost maximum flow?

Prompt and context

Each directed edge has capacity and unit cost. Send up to a limit of flow from s to t, minimizing cost among solutions with the same flow. Return actual flow and cost while handling residual reverse edges, negative costs, parallel edges, unreachable sinks, and integer overflow.

What the interviewer is testing

• Whether you build residual edges and reverse costs correctly.
• Whether you can use successive shortest paths or potentials with negative edges.
• Whether you separate the maximum-flow objective from the minimum-cost tie-breaker.
• Whether you state complexity, overflow limits, and property-based tests.

Clarifying questions before answering

Confirm integer capacities and costs, allowed negative-cost cycles, exact-limit requirements, graph size, and cost bounds. If negative cycles are allowed, clarify whether unbounded cost reduction is part of the model and how initial potentials are obtained.

30-second answer framework

For every input edge, add a forward residual edge and a zero-capacity reverse edge with negated cost. Repeatedly find the shortest s-to-t path in the residual graph and augment its bottleneck until the limit is met or no path remains. If costs can be negative, compute initial potentials with Bellman-Ford, then reweight edges so Dijkstra is valid. Complexity depends on augmentations and the shortest-path implementation, not just on ordinary max-flow complexity.

Step-by-step deep dive

1. Residual edge structure

Store destination, reverse index, residual capacity, and cost. Augmentation decreases forward capacity, increases reverse capacity, and adds flow times cost to the total. Reverse edges let later paths undo earlier choices, which is essential for optimal cost.

2. Shortest paths and potentials

With non-negative costs, Dijkstra is sufficient. With negative costs but no negative cycle, maintain a potential per vertex, compute shortest paths using reduced costs, then update potentials. Never apply ordinary Dijkstra directly to a graph containing negative edges.

3. Augmentation and stopping

The augmentation amount is the minimum of remaining limit, path bottleneck, and any batch cap. Stop when no path exists and return actual flow; if the exact limit is required, report infeasibility. Use a wide integer type and check multiplication before accumulating cost.

High-quality sample answer

I would store residual edges in adjacency lists and add each forward and reverse pair together. The main loop finds a shortest s-to-t path among positive-capacity edges, augments it, and updates cost. Dijkstra works for non-negative costs; with negative costs and no negative cycle, compute initial potentials and keep reduced costs non-negative. Limit each augmentation by remaining demand and path bottleneck. If the sink becomes unreachable, return actual flow and mark an unmet target infeasible. Tests cover reverse cancellation, parallel edges, zero capacity, negative costs, disconnected graphs, partial flow, negative-cycle assumptions, and large-cost overflow. The model matches OR-Tools' minimum-cost flow formulation, but complexity must name vertex, edge, and augmentation factors; it is not automatically polynomial in numeric capacities.

Common mistakes

• Forgetting reverse edges or assigning them a positive rather than negated cost.
• Running Dijkstra directly when residual edges can have negative cost.
• Augmenting only one unit per shortest path without justification.
• Treating maximum flow and minimum cost as one undifferentiated sort key.
• Accumulating large capacity-times-cost values in a narrow integer type.

Follow-up questions and responses

Why can a reverse edge fix an earlier choice?

It represents withdrawing previously sent flow and negates that flow's cost. A later shortest path can use it to rearrange the solution and lower total cost.

When do you need Bellman-Ford?

When the initial residual graph has negative-cost edges but no negative cycle, use it or an equivalent method to compute initial potentials; afterward non-negative reduced costs allow Dijkstra.

What if the requested flow cannot be reached?

Stop and return actual flow and cost with an explicit infeasible result. If the business requires the target, the caller must roll back or choose a fallback network rather than treating partial flow as success.