Search code examples
algorithmmax-flowfastflow

What does the level graph in Dinic's algorithm represent?


I understand what a residual graph is. But what does a level graph mean? http://en.wikipedia.org/wiki/Dinic%27s_algorithm


Solution

  • 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.