Hello all,
Hope you all are fine. Recently i am learning about Dinic algorithm, but it is little tough for me to understand alone, can anyone please tell me about what is happening in the "Example" part of http://en.wikipedia.org/wiki/Dinic's_algorithm, i did Edmonds-karp algorithm earlier.
I found that there are two new concept in this algorithm,
1. Layered Graph.
2. Blocking Flow.
please tell me why actually i should use Layered Graph here ?? and also please tell me how to find blocking flow. I have googled for dinic algorithm but didn't find anything that would satisfy me. Looking for some one to reply me.
Thanks.
why O(n) edges? there is O(e) edges in full graph, and in layered graph too.
one step of dinnic algorithm
1) d[s] = 1, d[i] = inf, then use bfs to find shortest paths
2) use Edmonds-karp algorithm to find maximum flow in graph, using only edges (u, v) such that d[u] + 1 = d[v]
I read the dinic in wikipedia too, doesn't contains a proof about complexity...
What I understand was to "build" a new graph, (using a bfs) to allow the search to a new flow over some edges specifically (using dfs). And it's fast! A good problem to test a solution it's FASTFLOW (spoj), and here a lot of red guys discussion about it : click me