JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) Proof of successive shortest path algorithm
 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
 Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) Proof of successive shortest path algorithm Previous Thread  |  Next Thread