12.13 Minimum-Cost Maximum-Flow

Problem

Traditional maximum-flow algorithms answer a single question:

How much flow can be sent from the source to the sink?

They do not care where that flow travels.

Consider the network:

        cost=1
    A ----------> T
   /
S
   \\n    B ----------> T
        cost=10

Both paths have capacity:

A maximum-flow algorithm sees no difference between them.

However, in practice the paths may represent:

Transportation routes
Communication links
Manufacturing processes
Energy networks
Delivery schedules

The amount of flow matters, but so does the cost of transporting it.

The new objective becomes:

Send the maximum possible flow while minimizing the total transportation cost.

This is the minimum-cost maximum-flow problem.

Solution

Extend the flow network by assigning a cost to every edge.

Each edge now has:

Capacity
Cost

Example:

Edge	Capacity	Cost
S → A	10	0
A → T	10	1
S → B	10	0
B → T	10	10

Sending one unit through:

S → A → T

costs:

Sending one unit through:

S → B → T

costs:

The algorithm prefers cheaper routes whenever possible.

Cost of a Flow

For a flow assignment:

f(u,v)

with edge cost:

cost(u,v)

the total cost is:

Σ f(u,v) × cost(u,v)

summed over all edges.

Example:

Edge	Flow	Cost
S → A	5	2
A → T	5	3

Total:

5×2 + 5×3 = 25

The objective is to minimize this quantity.

Residual Networks with Costs

Residual graphs continue to play a central role.

Forward residual edges retain the original cost.

Example:

A → B
capacity = 10
cost = 4

creates residual edge:

A → B
cost = 4

Reverse residual edges receive the negated cost.

B → A
cost = -4

The negative cost is important.

Removing one unit of flow from a costly edge effectively refunds its cost.

Residual networks therefore support both:

Adding flow
Replacing expensive flow with cheaper alternatives

Successive Shortest Path Method

The most common minimum-cost flow algorithm repeatedly:

Finds the cheapest augmenting path.
Pushes as much flow as possible.
Updates the residual graph.
Repeats.

This is called the successive shortest path algorithm.

The structure resembles Ford-Fulkerson:

find path
augment
repeat

The difference is that paths are chosen by minimum cost rather than arbitrary reachability.

Example

Network:

Edge	Capacity	Cost
S → A	5	1
A → T	5	1
S → B	5	3
B → T	5	2

Possible routes:

Path	Cost per Unit
S → A → T	2
S → B → T	5

First Augmentation

Shortest-cost path:

S → A → T

Capacity:

Push:

Cost added:

5 × 2 = 10

Second Augmentation

The first path is saturated.

Remaining cheapest path:

S → B → T

Push:

Cost added:

5 × 5 = 25

Total:

Flow:

Cost:

This is the minimum-cost maximum-flow.

Why Shortest Paths Appear

Suppose one additional unit of flow must be sent.

Every possible route has a cost.

Choosing the cheapest route minimizes the increase in total cost.

The problem therefore becomes:

minimum-cost augmentation

Repeated many times.

Shortest-path algorithms naturally emerge.

Negative Edge Costs

Reverse residual edges create negative costs.

Example:

A → B
cost = 5

Residual edge:

B → A
cost = -5

This means the residual graph may contain negative edges.

Ordinary Dijkstra's algorithm is no longer directly applicable.

Special handling is required.

Bellman-Ford Approach

The simplest solution uses Bellman-Ford.

Bellman-Ford supports:

Positive costs
Negative costs
Negative residual edges

Each augmentation:

Bellman-Ford
augment
repeat

Complexity:

O(FVE)

where:

F = flow value
V = vertices
E = edges

This is often too slow for large networks.

Potentials and Reduced Costs

A more efficient solution uses vertex potentials.

Assign:

π(v)

to every vertex.

Define reduced cost:

cost'(u,v)
=
cost(u,v)
+
π(u)
-
π(v)

The key property:

Reduced costs remain nonnegative.

Now Dijkstra's algorithm becomes usable.

This optimization is known as Johnson reweighting.

Dijkstra-Based Algorithm

With potentials:

Run Dijkstra.
Find cheapest augmenting path.
Update flow.
Update potentials.
Repeat.

Complexity improves significantly:

O(FE log V)

for sparse graphs.

This version is common in production implementations.

Example: Worker Assignment

Workers:

Alice
Bob

Tasks:

A
B

Costs:

Worker	A	B
Alice	1	10
Bob	2	3

Flow network:

source
↓
workers
↓
tasks
↓
sink

Capacities:

Worker-task edges receive assignment costs.

The resulting minimum-cost maximum-flow gives:

Worker	Task
Alice	A
Bob	B

Cost:

1 + 3 = 4

This is the optimal assignment.

The assignment problem can therefore be solved directly using min-cost flow.

Flow vs Cost Objectives

Different formulations exist.

Maximum Flow

Optimize:

maximize flow

Ignore costs.

Minimum-Cost Flow

Optimize:

minimize cost

for a fixed amount of flow.

Minimum-Cost Maximum-Flow

Optimize:

maximize flow

then:

minimize cost

among all maximum flows.

These objectives are related but not identical.

Detecting Negative Cycles

Residual graphs may contain cycles with negative total cost.

Example:

A → B = 3
B → C = -5
C → A = 1

Cycle cost:

-1

Such cycles indicate that the current flow can be improved without changing flow value.

Many advanced algorithms explicitly search for and eliminate negative-cost cycles.

Applications

Transportation

Ship goods while minimizing transportation cost.

Supply Chains

Move inventory through warehouses and distribution centers.

Airline Scheduling

Assign aircraft to routes while minimizing operating expenses.

Workforce Planning

Assign employees to shifts while minimizing labor costs.

Network Routing

Route traffic while minimizing congestion penalties.

Resource Allocation

Assign limited resources while minimizing total expense.

Implementation Pattern

Typical edge structure:

Edge {
    to
    capacity
    cost
    reverse
}

Residual update:

forward.capacity -= pushed
reverse.capacity += pushed

Costs remain:

forward.cost
reverse.cost = -forward.cost

This invariant is fundamental.

Complexity

Using Bellman-Ford:

O(FVE)

Using Dijkstra with potentials:

O(FE log V)

Using more advanced scaling methods:

near-linear practical performance

for many sparse networks.

Common Mistakes

Forgetting Reverse Costs

Residual reverse edges must use:

-cost

not the original cost.

Running Plain Dijkstra

Negative residual costs invalidate ordinary Dijkstra.

Use Bellman-Ford or potentials.

Mixing Objectives

Maximum flow and minimum cost are separate objectives.

Be explicit about which optimization problem is being solved.

Ignoring Integer Overflow

Costs and flows are multiplied together.

Large instances often require 64-bit arithmetic.

Discussion

Minimum-cost maximum-flow generalizes many earlier problems in this chapter. Bipartite matching becomes unit-capacity min-cost flow. Assignment becomes min-cost flow. Transportation, scheduling, and allocation problems frequently become flow networks with costs.

This modeling flexibility explains why minimum-cost flow is one of the most useful optimization tools in algorithm design. Once a problem can be expressed as flow moving through a network with capacities and costs, a wide range of allocation and planning problems become solvable using a common framework.

Takeaway

Minimum-cost maximum-flow extends maximum flow by assigning costs to edges and minimizing the total cost of transporting flow through the network. The core idea is simple: repeatedly augment along the cheapest residual path until no further improvement is possible.

This framework unifies matching, assignment, transportation, scheduling, and resource allocation problems. The next recipe generalizes flow further by removing the distinction between source and sink entirely, leading to circulation networks with demands and lower bounds.