Package com.jgalgo.alg.flow

Class 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 Detail

      • 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.