Minimum-Cost Network Flow Optimizer

Demand & Network

Flow demand (source → sink) 12

Edge capacity scale 1.0×

Flow animation speed 1.0×

Min-Cost Flow Result

Total cost

Flow delivered

0 / 0

Augmenting paths

Saturated edges

0 / 0

How it works

This is the minimum-cost flow problem: push a required amount of flow D from a source node to a sink node across a directed network where every edge (u,v) has a capacity cap(u,v) and a per-unit cost cost(u,v), minimizing total cost while respecting every capacity and conserving flow at every intermediate node.

It is solved here with the successive shortest augmenting path (SSP) algorithm:

while remaining demand > 0:
  find the cheapest path source→sink
  in the residual graph (Bellman-Ford,
  since reverse residual edges carry
  negative cost)
  if no path exists: infeasible, stop
  bottleneck = min(remaining demand,
                    min residual capacity on path)
  push `bottleneck` units along the path
  totalCost += bottleneck * path cost
  remaining -= bottleneck

Each augmentation opens a reverse "undo" edge of negative cost equal to -cost(u,v) and residual capacity equal to the flow just pushed, which is what lets a later, cheaper path reroute flow away from an edge chosen earlier. Because the first Bellman-Ford pass runs on non-negative costs and every later pass only ever needs to handle those synthetic negative reverse edges, this greedy "always take the currently cheapest augmenting path" strategy is provably optimal — it is a textbook application of the max-flow min-cost duality used in logistics routing, telecom bandwidth allocation and airline crew scheduling.

Demand slider — how many units must reach the sink; raising it beyond total capacity leaves the network infeasible (delivered < demand).
Capacity scale — rescales every edge's capacity, showing how a congested network reroutes flow onto costlier detours once cheap edges saturate.
Regenerate network — draws a fresh random topology, capacities and costs (seeded, so re-running the algorithm on it is deterministic).
Edge brightness/thickness of color = utilization (flow ÷ capacity); particles stream along every edge actually carrying flow, faster on higher-utilization edges.

Source Sink Relay node Edge carrying flow

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.