Dinic's algorithm for Maximum flow in a graph

graph-algorithm
maximum-flow
dinics-algorithm

(Team) #1

Reading time: 15 minutes | Coding time: 9 minutes

Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network. The basic principle is that a Maximum flow = minimum cut and Breadth First Search is used as a sub-routine.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/dinics-algorithm/