Package com.jgalgo.alg.flow

Class MaximumFlowDinic

java.lang.Object
com.jgalgo.alg.connect.MinimumEdgeCutStAbstract
com.jgalgo.alg.flow.MaximumFlowAbstract
com.jgalgo.alg.flow.MaximumFlowAbstractWithResidualNet
com.jgalgo.alg.flow.MaximumFlowDinic
All Implemented Interfaces:
MinimumEdgeCutSt, MaximumFlow
public class MaximumFlowDinic extends MaximumFlowAbstractWithResidualNet
Dinic's algorithm for maximum flow.

The algorithm finds a maximum flow by repetitively finding a blocking flow in the residual network. It runs in \(O(m n^2)\) time and use linear space.

Based on the paper 'Algorithm for solution of a problem of maximum flow in a network with power estimation' by Y. A. Dinitz (Dinic).

Author:
Barak Ugav
See Also:

  • Constructor Details

    • MaximumFlowDinic

      public MaximumFlowDinic()
      Create a new maximum flow algorithm object.

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