How does Dinic's Max Flow compute the blocking flow in O(NM) complexity ?

Revision en3, by Maxon5, 2017-05-20 07:42:17

I've been trying to understand Dinic's Max Flow algorithm. I think I've fairly understood how the algorithm works.

In each iteration, you create a level graph using BFS and then find blocking flow in that level graph. You would need O(N) iterations and in each iteration, blocking flow can be found in O(NM) complexity. This is the place where I'm stuck. I've seen some implementations like Stanford Notebook Dinic implementation . But it seems to me that in the worst case you might need O(M^2) complexity to find the blocking flow if you implement the code this way. Can anyone help me to understand why the complexity is O(NM) for finding blocking flow ?


  Rev. Lang. By When Δ Comment
en3 English Maxon5 2017-05-20 07:42:17 4
en2 English Maxon5 2017-05-20 07:06:06 34 Tiny change: 'ld need **_O(N)_** iteration' -> 'ld need ** _O(N)_ **\n==== iteration'
en1 English Maxon5 2017-05-20 00:47:00 806 Initial revision (published)