Package com.jgalgo.alg.flow

Class MinimumCostFlowCycleCanceling

java.lang.Object
com.jgalgo.alg.flow.MinimumCostFlowAbstract
com.jgalgo.alg.flow.MinimumCostFlowAbstractBasedSourceSink
com.jgalgo.alg.flow.MinimumCostFlowCycleCanceling
All Implemented Interfaces:
MinimumCostFlow
public class MinimumCostFlowCycleCanceling extends MinimumCostFlowAbstractBasedSourceSink
Compute the minimum-cost (max) flow in a flow network using cycle canceling.

Firstly, a maximum flow is computed using MaximumFlow. Then, the residual graph is constructed from the max flow (containing only non-saturated edges), and negative cycles (with respect to the cost function) are eliminated from it repeatedly until no negative cycles remain.

The algorithm runs in \(O(CC) \cdot O(mCU)\), where \(O(CC)\) is the running time of the algorithm used to find a cycle in the residual graph, \(C\) is the maximum (absolute) edge cost and \(U\) is the maximum edge capacity.

Based on 'A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems' by M Klein (1966).

Author:
Barak Ugav

  • Constructor Details

    • MinimumCostFlowCycleCanceling

      public MinimumCostFlowCycleCanceling()
      Create a new minimum-cost flow algorithm object.

      Please prefer using MinimumCostFlow.newInstance() to get a default implementation for the MinimumCostFlow interface.