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