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:

• Wikipedia

Constructor Summary

Constructors

Constructor	Description
MaximumFlowDinic()	Create a new maximum flow algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.flow.MaximumFlowAbstract

computeMaximumFlow, computeMaximumFlow

Methods inherited from class com.jgalgo.alg.connect.MinimumEdgeCutStAbstract

computeMinimumCut, computeMinimumCut

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.