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 optimality
 Proof of optimality | Reply The article says, for the shortest path method, proving that no negative cycle occurs is the proof for optimality. I am afraid I am not getting the point. Why this should prove optimality? What prevents us from finding another solution with less cost?
 Re: Proof of optimality (response to post by prunthaban) | Reply (I didn't read the article, but here's how the proof I know goes) Take any other solution X, subtract the solution Y obtained by our method from that solution. Since the total flow was the same, the result X-Y is a circulation in the residual network of flow Y. And since no negative cycle exists in that network, and that any circulation can be represented as a sum of cycles, the cost of the circulation is non-negative, hence the cost of X is not less than the cost of Y.
 Re: Proof of optimality (response to post by Petr) | Reply I'm missing something. Can I in the exactly same way prove that cost of Y is not less than the cost of X?
 Re: Proof of optimality (response to post by ika) | Reply Bosses.. Sorry for irrelevant post..But i badly need to know it.ret >?= i;error C2059: syntax error : '?'>?= .... cann't i use this sign in microsoft visual c++ 6.0
 Re: Proof of optimality (response to post by SHAHEEN_SETU) | Reply It's a deprecated extension that was in earlier versions of gcc, but now has been removed. The TopCoder servers still allow its use.For your purposes, replace a
 Re: Proof of optimality (response to post by ika) | Reply No, because X can contain negative cycles.
 Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) Proof of optimality Previous Thread  |  Next Thread