I understand what a residual graph is. But what does a level graph mean? http://en.wikipedia.org/wiki/Dinic%27s_algorithm
From the Wikipedia article, the level graph is the subgraph of the residual graph with edges
E_L = {(u, v) in E_f : dist(v) = dist(u) + 1},
where E_f
is the set of edges in the residual graph, and dist(w)
is the unweighted distance from the source s
to w
.
In English, E_L
is comprised of the edges of the residual graph that belong to some unweighted shortest path from s
.