Graph algorithms / interactive lesson
Find a minimum-cost flow by starting from a feasible flow, scanning the residual network for negative-cost cycles, and canceling each cycle until no improving circulation remains.
About the algorithm
Cycle canceling is a method for minimum-cost flow. It starts with any feasible flow of the required value, then repeatedly finds a negative-cost cycle in the residual network and sends as much flow as possible around that cycle. Each canceled cycle preserves the flow value and lowers the total cost.
Minimum-cost flow algorithms grew from network optimization and linear programming research in the mid-20th century. Cycle canceling is one of the most conceptually direct algorithms because its optimality certificate is easy to state: a feasible flow is minimum-cost exactly when the residual graph has no negative-cost directed cycle.
First find a feasible source-to-sink flow of the requested value. Then build the residual graph: unused capacity creates forward residual arcs with the original cost, and existing flow creates backward residual arcs with the negated cost. If this residual graph contains a negative cycle, augmenting around it changes no net flow from source to sink, but it reduces the objective. The bottleneck is the smallest residual capacity on the cycle. Repeat until no negative cycle remains.
Minimum-cost flow models transportation, logistics, assignment with capacities, production planning, circulation problems, packet routing, scheduling, and many resource-allocation problems. Cycle canceling is often taught because it makes the residual-cost optimality condition very visual, even though faster algorithms such as successive shortest path with potentials or cost-scaling are preferred in large production systems.
Code companion
Connect each visual decision to an implementation pattern.
flow = any feasible flow of required value
build residual graph from flow
while residual graph contains a negative-cost directed cycle C:
delta = minimum residual capacity on C
augment delta units around C
update residual graph
return flow