Package com.jgalgo.alg.flow

Class MaximumFlowEdmondsKarp

java.lang.Object

com.jgalgo.alg.connect.MinimumEdgeCutStAbstract

com.jgalgo.alg.flow.MaximumFlowAbstract

com.jgalgo.alg.flow.MaximumFlowAbstractWithoutResidualNet

com.jgalgo.alg.flow.MaximumFlowEdmondsKarp

All Implemented Interfaces:

MinimumEdgeCutSt, MaximumFlow

public class MaximumFlowEdmondsKarp
extends MaximumFlowAbstractWithoutResidualNet

The Edmonds-Karp algorithm for maximum flow.

The most known implementation that solve the maximum flow problem. It does so by finding augmenting paths from the source to the sink in the residual network, and saturating at least one edge in each path. This is a specification Ford–Fulkerson method, which chooses the shortest augmenting path in each iteration. It runs in \(O(m^2 n)\) time and linear space.

Based on the paper 'Theoretical improvements in algorithmic efficiency for network flow problems' by Jack Edmonds and Richard M Karp.

Author:

Barak Ugav

See Also:

• Wikipedia

Constructor Summary

Constructors

Constructor	Description
MaximumFlowEdmondsKarp()	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

MaximumFlowEdmondsKarp

public MaximumFlowEdmondsKarp()

Create a new maximum flow algorithm object.

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