1
$\begingroup$

During the run of Ford Fulkerson algorithm if we label each vertex with d(v) where it means the shortest path distance from source to vertex v in residual graph. Is it possible that for some vertex this value decreases at any execution stage? I tried to find such an example, but it seems the vertices are getting away after each iteration from the source. Could you provide some example or at least starting point how to prove it?

$\endgroup$
1
  • $\begingroup$ The distance can decrease. You have to find an example where at a later iteration the back-edge that is introduced into the residual graph for any flow is used. This works for the Ford-Fulkerson-Algorithm but not for the Edmonds-Kapr-Algo. $\endgroup$
    – plshelp
    Oct 18, 2022 at 16:54

1 Answer 1

1
$\begingroup$

Consider the following flow graph and associated residual graph: G1

In this graph, $d(3) = 3$.

If you saturate the augmenting path $(s, 1, 2, 3, 4, t)$, then the graph and residual graph become: G2

In this graph, $d(3) = 2$, so it decreased.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.