Module toolbox_rs::dinic
source · [−]Expand description
A Max-Flow computation implementing Cherkassky’s variant of Dinitz’ seminal algorithm. The implementation at hand is distinguished by three factors:
- Computing the layer graph in a single BFS starting in t.
- Omitting maintenance of the layer graph.
- Running the augmentation phase as a single DFS.
The DFS restarts after it found an augmenting path on the tail of the saturated edge that is closest to the source.