View source for Negative cycle-canceling

== Abstract view ==

'''Algorithmic problem:''' [[Min-cost flow problem]]

'''Type of algorithm:''' loop

'''Invariant:''' The flow is feasible.

'''Variant:''' The cost of the flow decreases.

'''Definition:'''
A cycle is '''negative''' if the sum of the cost values on all of its arcs is negative.

'''Break condition:''' There is no more negative cycle in the residual network.

== Induction basis ==

'''Abstract view:''' Start with an arbitrary feasible flow, for example, the zero flow.

== Induction step ==

'''Abstract view:'''
# Find a [[Basic graph definitions#Cycles|cycle]] of negative cost in the [[Basic flow definitions#Residual network|residual network]].
# Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle.

'''Implementation:'''
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm.
# If the distance <math>v\rightarrow v</math> is 0 for all <math>v\in V</math>, the break condition applies.
# Otherwise (that is, the distance is negative),