Overview
Min-cost max-flow keeps capacities and per-unit costs in the residual network, repeatedly sending flow along cost-improving residual paths until no more flow can be sent or the requested amount is reached.
CoreSource checked
Min-Cost Max-Flow
Finds a maximum feasible flow whose shipped units have minimum total cost.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Network Flow
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
flow networkresidual graphedge costreduced costpotentialsuccessive shortest path
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(V^2 E)
Worst
O(V^2 E)
Space
O(V + E)
When to Use
- Use when the objective is to send as much required flow as possible at minimum cost.
- Use when costs, capacities, supplies, and demands can be modeled as a flow network.
When Not to Use
- Avoid when edge costs are irrelevant; a plain maximum-flow algorithm is simpler.
- Avoid when lower bounds, negative cycles, or supplies/demands are needed but unsupported by the chosen variant.
What It Does
- Optimizes both amount of flow and total transportation cost.
- Maintains residual capacities with reverse edges that undo flow at negative cost.
- Uses shortest-path or cycle-canceling subroutines depending on the implementation variant.
Use Cases
- Assignment, routing, and scheduling models with capacities and per-unit costs.
- Flow networks where maximum throughput alone is not enough.
- Small or structured networks where repeated residual shortest paths are acceptable.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Key Formulas (1)
Reduced cost
c'(u,v) = c(u,v) + π[u] − π[v]
c'(u,v) = c(u,v) + pi[u] - pi[v]Uses potentials to keep shortest-path costs nonnegative in the residual graph.
Pseudocode
- 1.Initialize zero flow and residual edges with costs
- 2.While additional required flow remains
- 3.Find a cheapest residual path from source to sink
- 4.If no path exists, stop with the flow sent so far
- 5.Augment by the minimum residual capacity and remaining demand
- 6.Update forward and reverse residual capacities
- 7.Return total flow and total cost
Canonical Example
- Input
- send 1 unit from s to t; path s-a-t costs 5, path s-b-t costs 2, both have capacity 1
- Output
- send the unit through s-b-t with total cost 2
- Explanation
- The cheapest residual path with enough capacity satisfies the requested flow at lower cost.
Implementation Notes
- Store capacity, cost, reverse-edge index, and current residual capacity together.
- After every augmentation, update both forward and reverse residual edges.
- Use Bellman-Ford or initial potentials if negative residual costs can appear before Dijkstra is valid.
Common Pitfalls
- Reverse residual edges must have the opposite cost of the forward edge.
- Dijkstra-based variants need valid potentials so reduced costs stay nonnegative.
- Maximum flow and minimum-cost fixed-amount flow are related but not identical problem statements.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow augmenting flow along cheapest residual paths until the desired flow is reached on a small minimum-cost flow example.
Step 1 of 7: Initialize zero flow and residual edges with costs
optimization-mechanismNotes
Min-cost max-flow has several variants; shortest-path implementations need careful potential and residual-cost handling.
Sources (2)
What each reference supports for this entry.
Network Flows: Theory, Algorithms, and Applications
BookReference for Min-Cost Max-Flow's network-flow, cut, residual-network, or matching formulation.
Introduction to Algorithms (CLRS)
BookTextbook support for Min-Cost Max-Flow's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesHungarian Algorithm
Optimization · Core
Both address assignment problem, but they make different modeling or performance tradeoffs.
Compare with thisOften paired withDijkstra's Algorithm
Pathfinding · Foundation
Successive-shortest-path variants often use Dijkstra with potentials for nonnegative reduced costs.
Compare with thisRelationships
View full relationship pageGeneralizesFord-Fulkerson
Min-cost max-flow extends residual-network augmentation with per-unit edge costs.
Conceptual neighborEdmonds-Karp
Both augment through residual networks, but min-cost max-flow chooses paths by cost rather than hop count.
Often paired withDijkstra's Algorithm
Successive-shortest-path variants often use Dijkstra with potentials for nonnegative reduced costs.
Related Algorithms
Tags
OptimizationNetwork FlowPriority Queue