Class Dinic¶

Inheritance Relationships¶

Class Documentation¶

class Dinic : public NetworKit::Algorithm¶

Computes maximum flow in a directed, weighted graph using Dinic’s algorithm.

This class implements the blocking flow approach of Dinic’s algorithm to compute the maximum flow from a given source to a target node.

Public Functions

Dinic(const Graph &G, node src, node dst)¶

Construct a Dinic flow solver.

Parameters:

• G – Reference to the input directed, weighted graph.

• src – Source node identifier.

• dst – Target node identifier.

Throws:

std::runtime_error – if the graph is not directed, not weighted, or src == dst.

virtual void run() override¶

Execute the algorithm to compute maximum flow.

Initializes the residual graph, then repeatedly performs BFS to build level graphs and DFS to find blocking flows until no augmenting path remains.

edgeweight getMaxFlow() const¶

Retrieve the maximum flow value.

Throws:

std::runtime_error – if called before run().

Returns:

The computed maximum flow from source to target.