Dinic's algorithm, also called Dinitz's algorithm, is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by the Israeli computer scientist Yefim Dinitz. Like the Edmonds-Karp algorithm, it works by repeatedly finding shortest augmenting paths, but it introduces the concepts of the level graph and blocking flow to reach a better running time. It remains one of the standard textbook algorithms for the maximum flow problem.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.