Is Dinitz a shortest-path algorithm?

It uses shortest residual layers internally, but its objective is maximum flow.

Must every edge be saturated at the optimum?

No. Some capacity can remain unused behind other bottlenecks.

Can several maximum flows exist?

Yes. Different edge assignments can attain the same maximum value.

AI Glossary / Graphs and symbolic AI / Advanced

Dinitz

Definition

Dinitz is a maximum-flow algorithm that increases the amount of a single commodity sent from a source to a sink while respecting edge capacities and flow conservation. It works in stages using a residual network and layers of nodes. The name also appears as Dinic; this entry concerns the algorithm, following the supplied NetworkX reference.

What it means

Maximum flow asks how much can pass through a network, rather than which single route is shortest. Flow may be distributed across several routes, and intermediate nodes must pass on as much as they receive. Edge capacities limit the amount assigned to each connection.
The answer applies to the modeled network and its assumptions. The algorithm does not automatically account for travel times, competing commodity types, storage, or scheduling rules.

How it works

Begin with zero flow and construct a residual network. Forward residual capacity indicates how much more flow an edge can accept. Reverse residual capacity represents the ability to cancel some previously assigned flow and reroute it; it is not necessarily a physical reverse connection.
Breadth-first search assigns levels according to the number of residual edges from the source. The level graph retains positive-residual edges that advance exactly one level. The algorithm pushes flow through this graph until it has a blocking flow: every source-to-sink path in the level graph contains an edge with no remaining forward capacity for that stage.
It then rebuilds the levels using the updated residual network. A blocking flow ends a stage, not necessarily the whole calculation. Completion occurs when the sink is unreachable through positive residual capacity. NetworkX's dinitz function returns the residual network, including the flow value. An optional cutoff can stop computation before the maximum is established, so a cutoff result needs different interpretation.

Three practical examples

Transfer-capacity planning: A team models links with fixed capacities to estimate the largest supported transfer rate between two endpoints. Real congestion and protocol overhead require separate consideration before treating that mathematical value as an achievable operational rate.
Matching tasks to resources: A bipartite compatibility problem can be represented as a flow network with suitable capacities. Maximum flow then measures how many compatible assignments can be made. Preferences or differing assignment costs require more than maximizing assignment count alone.
Bottleneck analysis: An analyst studies a constrained distribution network. A completed maximum-flow calculation can support identification of a minimum cut, whose capacity limits total throughput. Increasing an arbitrary busy edge does not necessarily increase that limiting capacity.

Think of it this way

Imagine filling a network through its currently shortest available chains of connections, then rebuilding the picture of what capacity remains. Some earlier assignments can be revised to make room for better combinations. Finishing one collection of chains does not mean every possible route through the network has been exhausted.

Worked example

Consider a directed network with source S, sink T, and intermediate nodes A and B. Capacities are S-A = 3, S-B = 2, A-T = 2, B-T = 3, and A-B = 1. There are no other original edges, and all flows initially equal zero.
The first breadth-first layering places S at level 0, A and B at level 1, and T at level 2. The edge A-B connects two nodes at the same level, so it is excluded from this first level graph.
Send 2 units along S-A-T and 2 along S-B-T. The total flow is now 4. Every source-to-sink path in this level graph is blocked: A-T is saturated, and S-B is saturated. Nevertheless, the full residual network still contains the route S-A-B-T, with residual capacity 1 on each of its three edges.
Rebuild the layers and send 1 more unit along that route. The final original-edge flows are S-A = 3, S-B = 2, A-T = 2, A-B = 1, and B-T = 3. At A, inflow 3 equals outflow 2 + 1. At B, inflow 2 + 1 equals outflow 3. All capacities are respected.
The total value is 5. The cut separating S from all other nodes has capacity 3 + 2 = 5, so no feasible flow can exceed 5. The displayed flow reaches that bound and is therefore maximum.

Illustrative case study

Fictional Maple Transfers uses a flow model to compare capacity upgrades. An early dashboard labels the result after one layer-based stage as “maximum throughput.” A reviewer constructs a case where a longer residual route can carry additional flow.
The team changes the completion check to require that no residual source-to-sink route remains, unless the user explicitly requests an early threshold stop. It displays threshold attainment separately from an established maximum. Capacity units and the assumptions behind each modeled link are recorded alongside the result.

Common misconceptions and mistakes

“A blocking flow is always the maximum flow.” It can finish only the current level graph.
“Reverse residual edges mean goods physically travel backward.” They can represent cancellation of an earlier assignment.
“Maximum flow chooses the cheapest route.” It maximizes quantity under capacities, not a cost objective.
“A cutoff result proves optimality.” It may establish only that a requested threshold was reached.
“Adding all edge capacities gives throughput.” Conservation and network connectivity restrict what reaches the sink.

Business use

Specify the source, sink, capacity units, and meaning of intermediate nodes before running the model. Check whether splitting flow is appropriate and whether multiple kinds of demand compete for shared capacity. These modeling choices determine whether single-commodity maximum flow answers the business question.
Validate capacity constraints and flow conservation in returned results. When presenting an optimum, include a suitable bound or cut as supporting evidence and state whether early termination was used. Compare upgrade scenarios by their effect on the whole network.

Check your understanding

Why is A-B excluded initially?

Answer: A and B share the same breadth-first level.

Why is flow 4 not final?

Answer: The residual route S-A-B-T can carry another unit.

What proves the final value 5 is optimal?

Answer: A feasible flow of 5 matches the source cut's capacity of 5.

Related terms

Maximum Flow
residual network
blocking flow
level graph
augmenting path
minimum cut
flow conservation

Learn next

Trace residual capacities after each augmentation in the example. Identify reverse residual edges, rebuild the levels, and verify both node conservation and the cut bound before declaring the calculation complete.

Sources

NetworkX, dinitz reference and return conventions: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.dinitz.html NetworkX, Dinitz implementation and layered search: https://networkx.org/documentation/stable/_modules/networkx/algorithms/flow/dinitz_alg.html NetworkX, Dinitz's Algorithm and Applications: https://networkx.org/nx-guides/content/algorithms/flow/dinitz_alg.html

Previous: Dimensionality reduction Next: Diphthong