Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Flow & Matching  ›  Lesson

Min-Cost Flow & Assignment

Min-Cost Flow & Assignment 34 minPush each unit along the cheapest residual path, found with Bellman-Ford because reverse edges are always negative — and watch the assignment problem fall out as the special case where every pipe has capacity one
You're building a piece ofMeridian — the dispatcher
This piece — cheapest_dispatch(): Moves a given volume for the lowest total cost, routing the costliest units last.
Scenario Dispatch has an order to fill, not just a capacity to max out: 5 loads need to move, and every route costs something different per load. The cheap route alone can't carry all 5 — the question is how to fill the rest for as little as possible.
Your task
Build cheapest_dispatch(edges, source, sink, send). edges is a list of [from, to, capacity, cost]. Repeat: find the cheapest source-to-sink path with capacity left, using Bellman-Ford (residual reverse edges are negative-cost by construction). Push min(path's bottleneck, units still needed). Stop when no path exists or send is fully routed. Return {"flow": total pushed, "cost": total cost}. Example: cheapest_dispatch([["s", "a", 3, 1], ["a", "t", 3, 1]], "s", "t", 2) -> {"flow": 2, "cost": 4}.

Min-Cost Flow & Assignment

In short: Max flow asks how much can move. Min-cost flow asks how cheaply a given amount can move, when every pipe also has a price per unit. The algorithm is the familiar one, with the search for an augmenting path replaced by a search for the cheapest one: push units along the cheapest route with capacity left, update the residual graph, repeat. Because every reverse edge refunds its forward cost (its weight is the negative of the original), the residual graph always has negative edges — so the search uses Bellman-Ford, not Dijkstra, even though every pipe you started with had a non-negative cost. The assignment problem — pairing rows to columns for the least total cost — turns out to be the exact same algorithm on a network where every pipe has capacity one.

A tiny bipartite graph, r1 and r2 on the left, c1 and c2 on the right, every pipe capacity one, with costs 4, 1, 2 and 0 on the four pipes and a cost-matrix table beside it; r1-c2 plus r2-c1 is bolded at a total of 3, cheaper than r1-c1 plus r2-c2 at 4

From matching to pricing

Section 17's assign_drivers found the biggest matching, with no notion of one driver-job pairing being better than another. Give every pipe in that same network a cost — what it's worth to Meridian to have ana driving the truck instead of the van — and "the best assignment" becomes a min-cost flow question with every capacity equal to 1. The four-pipe graph above is exactly that: r1-c1 costing 4 instead of r1-c2 costing 1 is the difference between a good pairing and a bad one, and checking both totals (4 vs. 3) is the entire Hungarian algorithm's idea in miniature. A real Hungarian solver avoids trying every permutation; this lesson's exercise uses permutations directly, since the matrices Meridian deals with here are small enough that it doesn't matter.

Why the residual graph needs Bellman-Ford

Pushing 4 units along a pipe that costs 1 per unit opens a reverse edge that costs −1 per unit — undoing a unit should refund what it cost, the same way undoing capacity should return it. That −1 is not a special case; it's true of every reverse edge, every time, even on a network where every original cost is positive:

python

Dijkstra assumes every edge weight is non-negative, which the residual graph breaks on the very first push. Bellman-Ford tolerates negative weights as long as there's no negative cycle — and a min-cost flow network never develops one, because a cycle that paid you to go around it would mean the flow you already had wasn't actually cheapest, a contradiction.

Watch it on the depot network

Costs: depot-dock and dock-axle are cheap (1 each), depot-mill is dear (3), axle-harbour is 2, and the berth detour is the dearest hop (4):

watch it move · graph

Edges badged with (capacity, cost). Each round finds the cheapest residual path and pushes its full bottleneck.

Send 5 units from depot to harbour for the least total cost. Costs: depot-dock 1, dock-axle 1, axle-harbour 2, depot-mill 3, mill-axle 1, dock-berth 4, berth-harbour 1. 6 nodes, 7 edges, directed. At depot.

1 / 4

The second path reuses the exact backward edge from lesson 1 — but this time it's not just freeing capacity, it's worth doing even though it looks like a detour, because the refund makes the full route cheaper than any alternative that avoids axle-dock entirely.

In code

python

Quick practice

What does this print?
# two routes: s-a-t at 1+1 per unit, s-b-t at 1+3 per unit
cheap_route = 1 + 1
dear_route = 1 + 3
# send=4 but each route only has capacity 3 -- 3 go cheap, 1 is forced dear
total_cost = 3 * cheap_route + 1 * dear_route
print(total_cost)
broken — fix it

push_with_cost updates capacity correctly but leaves cost untouched. Fix it so it also sets cost[b][a] = -cost[a][b] on every push.

Why min cost, not max flow, is the real question

A pure max-flow run doesn't care which route it uses, only that it finds a path with capacity. Min-cost flow adds a tiebreaker — among every way to reach the same total, prefer the cheapest — and that tiebreaker is why real logistics software runs this and not plain Edmonds-Karp. Meridian's dispatcher in the capstone leans on exactly this: not just "can 5 loads move", but "what's the least it costs to move them."

Finds Needs
Max flow the most that can move BFS (Edmonds-Karp) or level graphs (Dinic)
Min-cost flow the cheapest way to move a given amount Bellman-Ford, because residual costs go negative
Assignment the cheapest 1-to-1 pairing min-cost flow with every capacity 1

❓ Cross-question: "What if I just want the cheapest way to max out the flow, not a fixed amount?" Set send to the network's actual max flow (lesson 1's push_volume), or just let the loop run until no augmenting path exists at all — both give the min-cost maximum flow.

🎯 Your turn

Write cheapest_dispatch(edges, source, sink, send). edges is a list of [from, to, capacity, cost]. Push each unit along the cheapest residual path (Bellman-Ford) until send units have moved or no path remains:

  • cheapest_dispatch([["s", "a", 3, 1], ["a", "t", 3, 1]], "s", "t", 2) → {"flow": 2, "cost": 4}

Hint: track capacity and cost together per directed pair; a reverse edge starts at capacity 0 and cost -w.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's dispatcher is built. ✅

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upWhat does this route cost per unit

Write route_cost(edges, path) where edges is a list of [from, to, capacity, cost] and path is a list of nodes. Return the sum of the per-unit costs along path, or None if some step has no matching edge. Example: route_cost([["s", "a", 3, 2], ["a", "t", 3, 1]], ["s", "a", "t"]) -> 3.

min-cost-flow
DrillHow much can this route carry

Write route_capacity(edges, path) returning the smallest capacity among the consecutive edges path uses (the usual bottleneck, this time on 4-element edges), or None if some step has no matching edge. Example: route_capacity([["s", "a", 3, 2], ["a", "t", 1, 1]], ["s", "a", "t"]) -> 1.

min-cost-flowmax-flow
BuildWhich of two routes wins

Write is_cheaper(edges, path_a, path_b) returning whichever of path_a or path_b has the lower total cost (route_cost's rule). Return path_a on a tie. Example: is_cheaper([["s", "a", 3, 1], ["a", "t", 3, 1]], ["s", "a", "t"], ["s", "t"]) is whichever actually costs less in that network.

min-cost-flow
BossCheapest cost to everywhere

Write bellman_ford_costs(edges, source) where edges is a list of [from, to, cost] (costs may be negative, but never form a negative cycle). Return a dict of the cheapest cost from source to every node IT CAN REACH (omit unreachable nodes entirely — don't try to represent infinity). Example: bellman_ford_costs([["a", "b", 2], ["b", "c", -1]], "a") -> {"a": 0, "b": 2, "c": 1}.

shortest-pathsmin-cost-flow
CapstoneThe Hungarian problem, by brute force

Write assignment_cost(cost_matrix), an n-by-n grid where cost_matrix[i][j] is the cost of assigning row i to column j. Return the lowest total cost of a perfect assignment — one row per column, one column per row. n is always small (at most 5), so check every permutation of columns. Example: assignment_cost([[4, 1], [2, 0]]) -> 1 (row 0 to column 1, row 1 to column 0: 1 + 2 = 3, versus row 0 to column 0, row 1 to column 1: 4 + 0 = 4 — wait, check both and take the smaller).

min-cost-flowhungarian
cheapest_dispatch.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
cheapest_dispatch(edges, source, sink, send) → dictHow much actually shipped, and the lowest total cost of shipping it.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.