Re: negative edge weights in case of Bellman-Ford algorithm

On Mar 26, 10:05 am, "GCRhoads" <rho...@xxxxxxxxxxxxxxx> wrote:
On Mar 22, 8:18 am, "kris" <raghavakrishn...@xxxxxxxxx> wrote:

How can we have negative edge weights in case of weighted graphs.
what are the negative cost cycles in the graph? How can we have
negative cost cycles in a graph?

Book: Introduction to algorithms: Cormen et al. This question is
answered quite well out there!

That depends on the application. For most applications, negative
edge weights and negative cycles don't make physical sense but
for some applications they do.

For example: When modeling a network, there exists a path which is
Owned by ABC organization, that charges per packet and the remaining
paths don't, the "negative" edge weight can be used to model the
expense/loss incurred.

Regards,

Nupul

.