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?
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$– plshelpCommented Oct 18, 2022 at 16:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider the following flow graph and associated residual graph:
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:
In this graph, $d(3) = 2$, so it decreased.
