Module maximum_flow

Collection of algorithms for the Maximum Flow Problem.

Both algorithms solve the maximum flow problem and compute the same maximum flow value, although they may differ in how much flow is assigned to each edge in the resulting flow.

dinics and ford_fulkerson have different time complexities, and their performance can vary significantly depending on the input graph. In general, dinics is faster, especially on dense graphs, graphs with unit capacities, and bipartite graphs. ford_fulkerson may be a better choice when working with small or sparse graphs.

For more information about each algorithm and their detailed time complexity, check their respective documentation.

Functions

dinics

Compute the maximum flow from source to destination in a directed graph. Implements Dinic’s (or Dinitz’s) algorithm, which builds successive level graphs using breadth-first search and finds blocking flows within them through depth-first searches.

ford_fulkerson

Ford-Fulkerson algorithm in the Edmonds-Karp variation. Computes the maximum flow from source to destination in a weighted directed graph.