JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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 <?= b with a = min(a,b)
Re: Proof of optimality (response to post by ika) | Reply
No, because X can contain negative cycles.
RSS