Dinic's algorithm

How many airports have to close at the same time, because of weather, a strike or ash after an eruption, for it to be impossible to fly from Almaty to Lima? As many as there are itineraries with no change of planes in common: each such itinerary has to be blocked separately, and that is enough. Below is the flight network of the whole world, 3468 airports and 84,869 routes, and Dinic's algorithm, which looks for these itineraries not one at a time but in phases. Tap any airport to change the destination.

From Almaty to Lima there are 52 itineraries, and no airport has two of them passing through it. Dinic needed nine phases. The first found one itinerary of two flights, through Amsterdam; the second 22 at once of three flights; the third 14 of four; after that fewer and longer ones. Switch to Edmonds–Karp: the same 52 itineraries, but 53 breadth-first searches instead of 10, and 7.2 million arc checks instead of 2.9.

The rings at the end mark the cut, 52 airports. Forty of them fly to Lima themselves. The other twelve, among them Frankfurt, Warsaw, Tenerife, Dakar, Lisbon and Recife, are changes through which itineraries pass to other airports that have a flight to Lima. Close all 52, and Lima cannot be reached from Almaty. Fewer will not do: exactly one of the 52 itineraries passes through each closed airport.

The captions to the steps tell something else too. Ten paths of the 52 take some flight backwards. This is not flying back but a cancellation: the flight is removed from an itinerary found earlier, that one continues another way, and there is one itinerary more. Every flow algorithm works like this; the article on maximum flow is about it.

The idea

Edmonds and Karp take the shortest augmenting path each time, and each path costs them a full breadth-first search. But shortest paths change slowly. After a search that found a path of three flights, the next couple of dozen paths will also have length three, and the search will find each of them anew, going over almost the same network. Dinic does one breadth-first search per path length.

Let d(v) be the distance in arcs from the source to v in the residual network. Keep only the arcs that lead exactly one layer deeper, from u to v with d(v) = d(u) + 1. This gives the layered network. Any path from source to sink along it is shortest, and conversely: every shortest path of the residual network lies in it entirely.

A blocking flow is a flow in the layered network such that on every path from source to sink along it at least one arc is saturated. It need not be maximum: inside the layered network there are no reverse arcs, what has been pushed cannot be cancelled, and an unlucky first path can close two good ones. The next phase fixes this.

Run a breadth-first search over the residual network and keep the arcs leading one layer deeper. Push paths along them with depth-first search until every path from source to sink runs into a saturated arc: that is a phase. Repeat phases while the sink is reachable.

The blocking flow is found by depth-first search, but with one detail without which it all makes no sense. Each vertex u has a pointer nxt[u], the index of the first outgoing arc still worth trying. If an arc is saturated or leads to a dead end, the pointer moves on and never returns to it in this phase. A vertex with no arcs left is a dead end: the search steps back, and the pointer of the vertex before it moves on too. Having found a path to the sink, the search pushes flow along it and starts again from the source, but the pointers remember everything discarded.

Here are the phases for the itineraries from Almaty to Queenstown. To keep the diagram readable, it shows only airports from which a path to the destination still exists inside the layers. The search visits the others too and steps back at once; they show only in the dead-end counter.

In the first phase Queenstown is at least three flights away, and the paths of that length pass through 27 airports with a direct flight from Almaty and 6 with a direct flight to Queenstown: Auckland, Christchurch, Brisbane, Gold Coast, Melbourne and Sydney. The search pushes six itineraries, one through each of the six. After that the flights from Almaty are still free, to 21 airports of the first column, but there is no way further: all six last changes are taken. The phase ends, although far from all the arcs have been gone through. The second phase builds the layers anew, and the shortest free path now has four flights: through Hong Kong, Nadi and Wellington. The third phase does not reach Queenstown. The answer is seven itineraries, and the cut of seven airports is exactly the seven with a flight to Queenstown.

The counter under the diagram shows the price. In the first phase the search in the real network stepped back 19,992 times, from airports from which Queenstown cannot be reached in the flights remaining. Almost the whole network is like that: in three flights from Almaty you can get almost anywhere, but to Queenstown only through six airports. Yet the search checked each dead end in full only once, and afterwards bounced off it in one step: the pointer was already at the end of its list of arcs.

Why there are few phases

Everything rests on one property: a phase moves the sink further away.

The distance is from 1 to V − 1 and grows by at least one with each phase, so there are at most V − 1 phases. It remains to see what one costs.

Together with the breadth-first search in O(E) per phase, this gives O(V² E) for the whole algorithm. Edmonds–Karp has the bound O(V E²): in a dense network, where E is close to V², the difference is a factor of V.

Unit networks

The airport network is special. Each airport, except the start and the end, is split into two vertices, arrival and departure, with an arc of capacity 1 between them, and all flights have capacity 1 too. This gives a unit network: all capacities equal 1, and every vertex except the source and sink has exactly one incoming arc (a departure) or exactly one outgoing arc (an arrival). No more than one unit can pass through such a vertex. Here Dinic is much faster than the general bound.

First, a phase costs O(E), not O(V E): when capacities are units, a path to the sink saturates all its arcs, and each arc is on a successful path at most once per phase. Then there are at most 2E steps forward. Second, there are few phases.

For the flight network V = 6936, and the bound promises at most 167 phases. In fact there are nine to Lima and three to Cape Town. The same theorem gives the bound for the Hopcroft–Karp algorithm: matching in a bipartite graph is a flow in a unit network of a source, two parts and a sink, and Hopcroft–Karp is exactly Dinic on it; details are in the article on matching. If only the capacities are units while many paths can pass through a vertex, Shimon Even and Robert Tarjan showed in 1975 that there are O(min(√E, V^2/3)) phases.

Code

The network is stored as in the article on maximum flow: arcs in pairs, the pair of arc a is a ^ 1, and the residual network is the array cap. An airport v becomes arrival 2v and departure 2v + 1. The breadth-first search stops when it reaches the sink's layer: deeper vertices would not get into the layered network anyway. The depth-first search is written without recursion, with a stack of the path's arcs: in a general network a path can be thousands of vertices long, and Python limits recursion depth to a thousand.

The number of flights in a path through the layers is (the sink's level + 1) / 2: the path goes along a flight arc, then along an arc inside an airport, and so on to the destination. At most one itinerary passes through each airport, so the flow decomposes into itineraries uniquely: at most one flight with flow leaves each airport. The shortest itinerary to Lima goes through Amsterdam, the longest is eight flights, through El Alamein, Katowice, Puerto Plata, Willemstad, Belo Horizonte, Bariloche and Mendoza. That is how far one has to go round when all the short paths are taken by other itineraries.

What it costs

A measurement on the same flight network. Take the k airports with the most routes and the flights between them, and count how many itineraries without common airports can run at the same time from the west (west of 30° W) to the east (east of 30° E). On the whole network there are 165 such itineraries. One more line is Dinic with a mistake: the pointers are reset after every path found.

On the whole network Dinic is 9.5 times faster than Edmonds–Karp in Python and 7.7 times in Go. Without the pointers almost nothing is left of this gain: each path tries all the dead ends anew, and a phase costs as many searches as it has paths.

The gain comes from a phase having many paths of the same length. If there are few paths, all of different lengths, there are almost as many phases as paths, and Dinic does the same work as Edmonds–Karp, and on top of that walks the layers in full rather than until it first hits the sink. For huge networks such as images other algorithms are more often used: Goldberg and Tarjan's preflow-push or the Boykov–Kolmogorov flow from the article on cuts.

Where it is easy to go wrong

• Forgetting the pointers. The most common mistake: depth-first search with “visited” marks that are reset before every path. The algorithm stays correct, but, as the measurement shows, loses almost all its speed.
• Moving the pointer after a successful path. If capacities are greater than one, an arc may remain unsaturated after a path, and another path will pass along it. The pointer moves only when the arc is saturated or leads to a dead end. In recursive implementations this looks like this: after a successful recursive call the function returns without moving the pointer.
• Recursion. Recursive search is shorter, but in Python the default depth is a thousand calls, and a path through the layers can be longer. Hence the stack in our code.
• Layers from the original network. Layers are computed on the residual network, with reverse arcs and without saturated ones. If they are built on the original network, there will be no cancellations, the answer may come out smaller than the maximum, and the stopping condition “the sink is unreachable” will never fire.
• Pointers from the previous phase. The pointers are reset at the start of each phase: the layers after it are different, and an arc discarded in the previous phase may now lead one layer deeper. If the array is set up once for the whole algorithm, a phase may find no path although the sink is reachable, and the algorithm loops forever.

Where it is used

Dinic's algorithm is the standard flow in competitive programming libraries. In the AtCoder Library the maximum flow function is this one: the arrays level and iter, breadth-first and depth-first search, and the documentation states O((n + m)√m) for unit capacities and O(n²m) in general. networkx has the function dinitz. Bipartite matching and vertex-disjoint paths are its special cases, and their bounds come from the theorem on unit networks. Even and Tarjan built a test of the vertex connectivity of a graph on it: how many vertices must be removed for the graph to fall apart is a minimum cut in a unit network, as in our scene with airports.

History

Yefim Dinitz devised the algorithm in January 1969, as a student in the group of Georgy Adelson-Velsky, the “AV” of AVL trees. It was the answer to an exercise in an algorithms course. The paper came out in 1970 and fitted into four pages, the journal's limit, so it turned out very terse. In the original version the layered network was a data structure that the algorithm maintained as it went, and the time was bounded by a subtle amortised analysis.

Shimon Even and the doctoral student Alon Itai became interested in Dinitz's paper and in a paper by Alexander Karzanov, where the notion of a blocking flow appeared. In three days they worked out both, except how to maintain the layered network. They filled this gap themselves: they took Karzanov's blocking flow and began to look for each path by depth-first search. Even then taught this version in lectures for years, and in this form, breadth-first search for the layers and depth-first search for the paths, the algorithm is taught today. In the English translation of the paper the surname was spelled Dinic, it was pronounced “Dinik” in lectures, and in English the algorithm is still called Dinic's algorithm. In 2003 Dinitz said that combining breadth-first with depth-first search was the merit of Even and Itai, and Even, when telling about the algorithm, added that Dinitz devised it at nineteen and was the first to publish an amortised bound on running time.

Independently of Dinitz, Jack Edmonds and Richard Karp showed in 1972 that shortest augmenting paths never get shorter: this is their theorem. Karzanov in 1974 found a blocking flow in O(V²) by pushing preflows, and the overall bound became O(V³). Then came the dynamic trees of Sleator and Tarjan and the preflow-push of Goldberg and Tarjan, and in 2022 an almost-linear-time algorithm, which the course chapter tells about.

Problems

The first problem needs only itineraries of the smallest length, and one phase is not enough for them: a blocking flow need not be maximum. In the second, thousands of names share three-letter codes, and the solution needs the bound for unit networks: one path per search will not finish in time.