Classes | Files

Minimum Cost Flow Algorithms

Algorithms

Detailed Description

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.

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.


 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines