Dinic's algorithm is a classical algorithm for the maximum flow problem, originating from an idea known as the Ford-Fulkerson method.
The core idea of the Ford-Fulkerson method resembles that of the Floyd-Warshall algorithm in that it uses a kind of alluvial-sand-style filtering strategy. It does not seek perfection in one stroke; rather, it keeps finding feasible paths in the residual graph in order to squeeze out the remaining flow.
func (ctx *contextL) dinic() uint {
flow := uint(0)
for ctx.separate() { //extract a subgraph (layered graph)
flow += ctx.search() //squeeze the remaining flow from the subgraph
ctx.flushBack() //merge the drained subgraph back into the original residual graph
}
return flow
}To make extraction easier, Dinic introduces a ranking system: first divide vertices into different levels, and then levy flow layer by layer. Vertices on the same level do not interact for the moment, but after each round of extraction some relations are always broken (because certain edges vanish), so the levels are reshuffled. As a result, no usable relation will be missed in the end.
A
A |
/ \ D
A - B - E B D A B - E / \
| / | / | => / \ / | / / | => B C
D - C - Z E C D - C Z \ /
\ / E
Z |
Z
The layer-separation process uses breadth-first search, and then discards vertices that are temporarily of no value:
func (ctx *contextL) separate() bool {
if !ctx.markLevel() { //mark vertex levels
return false
}
for curr := 0; curr < len(ctx.level); curr++ {
if ctx.level[curr] == fakeLevel {
continue
}
paths := ctx.origin[curr]
for i := 0; i < len(paths); i++ {
next := paths[i].Next
if ctx.level[next] == ctx.level[curr]+1 {
ctx.shadow[curr] = append(ctx.shadow[curr], paths[i])
paths[i].Weight = 0 //extract content from the main graph into the residual subgraph
} } }
return true
}We use depth-first search to probe for paths that can still be exploited:
func (ctx *contextL) search() uint {
for flow, stream := uint(0), uint(0); ; flow += stream { //each round deletes at least one edge of the subgraph
stream = math.MaxUint
ctx.stack.Clear()
for curr := ctx.start; curr != ctx.end; {
sz := len(ctx.shadow[curr])
if sz != 0 { //can move forward
ctx.stack.Push(memo{idx: curr, stream: stream}) //go deeper
path := ctx.shadow[curr][sz-1]
curr, stream = path.Next, utils.Min(stream, path.Weight)
} else { //hit a wall, step back
if ctx.stack.IsEmpty() { return flow } //nowhere left to retreat
tmp := ctx.stack.Pop()
curr, stream = tmp.idx, tmp.stream
last := len(ctx.shadow[curr]) - 1
fillBack(ctx.origin[curr], ctx.shadow[curr][last])
ctx.shadow[curr] = ctx.shadow[curr][:last]
}
}
for !ctx.stack.IsEmpty() { //process the augmenting path just found
tmp := ctx.stack.Pop()
curr := tmp.idx
last := len(ctx.shadow[curr]) - 1
path := &ctx.shadow[curr][last]
path.Weight -= stream //take away forward flow
ctx.reflux[path.Next] = append(ctx.reflux[path.Next],
graph.Path{Next: curr, Weight: stream}) //add reverse capacity to prevent greedy dead ends
if path.Weight == 0 {
ctx.shadow[curr] = ctx.shadow[curr][:last] //remove invalid residual edge
} } } }There is one point worth noting here: sometimes cutting an edge unexpectedly damages the connectivity of the graph. Physically, however, pipelines do not simply disappear; later we can obviously introduce reverse flow to offset the current choice of flow. In the algorithm, we must support the same possibility.
A → C → D A C → D A C → D
↓ ↓ ↓ => ↓ ↓ =(fix)=> ↓ ↑ ↓
B → E → F B → E F B → E F
We can see that the core of Dinic's algorithm is a cycle consisting of three operations: extracting a subgraph, squeezing out the remaining flow, and merging the residual structure back.
Among them, squeezing out the remaining flow consists of probing and cleanup. One cleanup pass traverses the recorded stack and costs O(V) operations, while at least one edge of the subgraph is deleted. Cleanup deletes edges as a result of successful probing. On the other hand, failed probing also gradually deletes edges on invalid paths in the subgraph, so the probing process itself always deletes edges from the subgraph. From this we can infer that the cumulative number of executions of the triple loop driving probing is O(E), and the number of executions of the outermost loop must be less than O(E).
Residual-edge recovery based on binary search costs O(logV), while graph merging based on merge operations costs O(E). In addition, extracting the subgraph costs O(E). Finally, we can readily derive the complexity of Dinic's algorithm:
O(E/k) × (O(E) + O(kV) × O(logV) + O(kV + E)) = O(V<sup>2</sup>E).
From the implementation point of view, the key to Dinic is not merely "finding one augmenting path", but first trimming the residual graph into a layered graph, and then repeatedly squeezing blocking flows out of that thinner graph.