Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Proof of successive shortest path algorithm | Reply
I'm a bit confused about the following part (proof of successive shortest path algorithm):

How could a negative cycle appear in a residual network?

Suppose that after augmenting the current flow x along path P a negative cost cycle W turned up in the residual network. Before augmenting there were no negative cycles. This means that there was an edge (i,j) in P (or subpath (i,…,j) in P) the reversal of which (j,i) closed cycle W after the augmentation. Evidently, we could choose another path from s to t, which goes from s to i then from i to j along edges of W then from j to t. Moreover, the cost of this path is less than the cost of P. We have a contradiction to the supposition that P is the shortest.

Why should there be the bold part? If (i,...,j) is a subpath, how should a reverse edge (j, i) be relevant since it is not added by the new augmented flow.
Re: Proof of successive shortest path algorithm (response to post by Duc) | Reply
i hope you are not missing the part that whenever you augment a path from s..i..j..t then an edge t..j..i..s is added to the network