Dinitz: a capacity-independent polynomial maximum-flow method using shortest-path referents

What is recorded here?

Dinitz organized shortest augmenting paths into a maintained layered referent, deleting saturated arcs and dead ends until the shortest source-to-sink distance increases, obtaining an O(n²m) arithmetic-operation maximum-flow bound. A maximum-flow algorithm must deliver as much flow as possible without exceeding capacities or losing flow at intermediate vertices. Arbitrary augmenting-path choices can take a number of steps tied to capacity magnitudes and can even fail to terminate with general real capacities. Dinitz’s 1970 article chooses shortest residual augmenting paths and maintains their union, called a referent. Each augmentation deletes at least one arc from the current shortest-path structure; recursively removing dead ends preserves the useful part. Once that structure is empty, the next shortest-path distance increases. There are fewer than n distance levels and only finitely many deletions at each level. The article bounds arithmetic/machine operations by O(n²m), independently of numerical capacity magnitudes. This is an exact-arithmetic model claim, not a bound on arbitrary-precision bit costs. The widely taught BFS-plus-DFS blocking-flow implementation is related but has a later contribution: the author’s retrospective credits Shimon Even and Alon Itai with that modification, using Karzanov’s blocking-flow concept. The current record assesses the original maintained-referent method rather than silently attributing every later implementation to 1970.

Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.

Scientific scope

The original method uses nonnegative capacities, opposite residual arcs and shortest-path referent maintenance. Its O(n^2 m) bound is an arithmetic/machine-operation count, not arbitrary-precision bit complexity or a measured modern runtime. Later DFS and blocking-flow modifications are credited separately. Finite graph tests do not independently certify the original amortized proof for every real-capacity network.

Read the original work

• E.A.Dinic, Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation —1970 English translation
• Yefim Dinitz, The Original Version and Even’s Version — author retrospective manuscript
• Yefim Dinitz institutional selected publications: historical E.A.Dinic spelling and1970 article

This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.

People and systems

Yefim Dinitz

Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.