Dinic's algorithm for Maximum flow in a graph


(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/