This group contains the algorithms for finding minimum cost flows and circulations [AMO93]. For more information about this problem and its dual solution, see Minimum Cost Flow Problem.

LEMON contains several algorithms for this problem.

- NetworkSimplex Primal Network Simplex algorithm with various pivot strategies [Dan63], [KO91].
- CostScaling Cost Scaling algorithm based on push/augment and relabel operations [GT90], [Gol97], [BKV98].
- CapacityScaling Capacity Scaling algorithm based on the successive shortest path method [EK72].
- CycleCanceling Cycle-Canceling algorithms, two of which are strongly polynomial [Kle67], [GT89].

In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. For example, if the total supply and/or capacities are rather small, CapacityScaling is usually the fastest algorithm (without effective scaling).

## Classes | |

class | CapacityScaling< GR, V, C, TR > |

Implementation of the Capacity Scaling algorithm for finding a minimum cost flow. More... | |

class | CostScaling< GR, V, C, TR > |

Implementation of the Cost Scaling algorithm for finding a minimum cost flow. More... | |

class | CycleCanceling< GR, V, C > |

Implementation of cycle-canceling algorithms for finding a minimum cost flow. More... | |

class | NetworkSimplex< GR, V, C > |

Implementation of the primal Network Simplex algorithm for finding a minimum cost flow. More... | |

## Files | |

file | capacity_scaling.h |

Capacity Scaling algorithm for finding a minimum cost flow. | |

file | cost_scaling.h |

Cost scaling algorithm for finding a minimum cost flow. | |

file | cycle_canceling.h |

Cycle-canceling algorithms for finding a minimum cost flow. | |

file | network_simplex.h |

Network Simplex algorithm for finding a minimum cost flow. |

Generated on Wed Nov 9 2011 11:44:10 by 1.7.3