Блог пользователя purple_dreams

Question in Dinic
Автор purple_dreams, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить