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... | |
struct | CapacityScaling< GR, V, C, TR >::SetHeap< T > |
Named parameter for setting Heap type. More... | |
struct | CostScaling< GR, V, C, TR >::SetLargeCost< T > |
Named parameter for setting LargeCost type. 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. | |