CONCEPT Cited by 1 source
Min-cost flow¶
Min-cost flow is a class of graph algorithms that find the lowest-cost way to push a specified amount of flow from a source node to a sink node through a directed graph where each edge has a capacity and a cost. It generalises shortest-path (push flow of 1 with a single cost) and max-flow (push as much as possible, ignoring cost).
The classic algorithms are successive shortest path (repeatedly
augment along the cheapest remaining path) and cycle-canceling
(push any flow, then repeatedly cancel negative-cost cycles).
Successive-shortest-path runs in O(V·E) per augmentation.
Real-world uses¶
- Order routing / fulfillment — deciding which warehouses or production sites ship which items of a multi-item order.
- Logistics — trucks, pallets, shipment routing.
- Transportation / assignment problems — workers → tasks, packets → paths.
- Layered production networks — products → production sites → delivery lanes, with capacity constraints at each layer.
Variants worth knowing¶
- Comparison-based costs (Canva). Canva's print routing replaces numerical cost accumulation with a Decision engine that pairwise-ranks candidate paths according to an ordered rule list. Traversal still follows the successive-shortest-path skeleton, but the inner comparison is delegated out — which makes cost logic independently swappable. (See systems/canva-print-routing, patterns/deterministic-rule-ordering.)
- Pre-filtering by zero-flow edges. Unwanted edges get capacity zero during preprocessing — they stay in the graph structurally but are invisible to traversal. This is how Canva applies hard constraints (e.g., "supplier can't print this product") before the decision engine ever runs.
- Flow-1 "visit-once" edges. Common trick to force each resource to be used at most once per augmentation.
Scaling levers¶
O(V·E) per augmentation is only tolerable when V and E are bounded.
Common tactics:
- Shard the graph by the query dimension — Canva shards by destination region (see concepts/geographic-sharding). A regional graph is small enough to fit in memory (Redis) and traverse in tens of milliseconds.
- Zero-flow filtering — shrinks the effective edge count.
- Pre-rank candidates by fewest-paths-forward — locks in constrained decisions early, avoiding backtracking cycles.
Seen in¶
- sources/2024-12-10-canva-routing-print-orders — modified successive-shortest-path min-cost-flow with pairwise-ranking decisions instead of numerical costs; shard-per-region graphs in Redis; p99 ~50 ms peak at Canva Print scale.