Referring to Tim Roughgarden's Lecture Note - 2 (page 11) on CS261 at Stanford following statement and the para seem quite confusing.

Claim: d(f) never decreases during the execution of the Edmonds-Karp algorithm.


Can anybody shed some lights on it?

Suppose the Edmonds-Karp algorithm augments the current flow f by routing flow on the path P . Because P is a shortest s-t path in Gf , it is also a path in the layered graph Lf . The only new edges created by augmenting on P are edges that go in the reverse direction of P . These are all backward edges, so any s-t of Gf that uses such an edge has at least d(f ) + 2 hops. Thus, no new shorter paths are formed in Gf after the augmentation.

  • 2
    $\begingroup$ 1. Can you edit the question to include all necessary context, so we can understand the claim and all notation and the excerpt you posted, without having to visit an external link? 2. What specifically are you confused about? What do you currently understand? Can you help us narrow down what you're unsure about, so we can be sure to address your specific issue? $\endgroup$ – D.W. May 23 '17 at 16:38
  • 2
    $\begingroup$ I'm not going to watch a lecture just in order to answer a question. $\endgroup$ – Yuval Filmus May 23 '17 at 18:26
  • $\begingroup$ It looks like you've answered why $\delta_f$ is monotonically non-decreasing. If you're wondering about the proof, CLRS is always a good resource. I would look at the Third Edition pages 727-730. $\endgroup$ – ryan May 24 '17 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.