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

Revision en3, by tanzon0xA5, 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 ?

History

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