purple_dreams's blog

Question in Dinic
By purple_dreams, history, 7 years ago, In English

In Dinic algorithm for maximum flow, we in dfs we write the function as

for(int &t = ptr[source]; t < neighbours of source ; ++t)

I read that ptr is an array used to make finding the blocking flow in O(m) rather than O(m2). Why does this work and what is the exact use of keeping the ptr array. How does this array work?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Suppose that using dfs for the first time after bfs you managed to send flow after exploring half of the nodes, next dfs will explore the same half again

However, with that array, ptr[u] is index of the last child of u that was being explored, you can resume from where you left off in previous dfs instead of starting all over again

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay so basically we do dfs only once. I mean we call it many times after finding the residual graph but the path we found out in the previous dfs won't be repeated again? Is what I understood correct? Basically the overall effect is that we do dfs only once?

    Thank you.

    → Reply