CODEWITHSUNDEEP
graphdijkstra
chum of chance
chum of chance

Reputation: 6300

Dijkstra's algorithm cannot deal with negative weights, when do you see negative weights in the real world?

I can't think of a concrete instance in which you'd have a negative weight. You cannot have a negative distance between two houses, you cannot go back in time. When would you have a graph with a negative edge weight?

I found the Bellman Ford algorithm was originally used to deal with routing in ARPANET, but again, can't imagine where you'd run into a route with a negative weight, it just doesn't seem possible. I could just be thinking too hard about this, what would be a simple example?

Upvotes: 3

Views: 2187

Answers (5)

Dave
Dave

Reputation: 6179

Even if there were an example; you could probably normalize it to be all positive. Any actual representation of a negative weight is relative to some 0. I guess what I'm saying is that there probably isn't an application of negative weights that can't be done using exclusively positive weights.

EDIT: After thinking about this a little bit more, I suppose you could have situations where a given path has a negative weight. In this context; assuming the negative weight is bad, you would have to have a situation where the only possible way to achieve the goal of getting to your desired endpoint, would mean there would have to be at least one point in your graph where you're REQUIRED to take the negative path (as in, no other option is available to reach your goal). But I suppose if the graph hasn't been traversed; how would you know it were true?

EDIT (AGAIN): @Jim, I think you're right. The choke point isn't really relevant. I guess I was too quick to assume that it was because one question that pops into my mind when introducing negative edges is - if it is possible to traverse the graph without taking ANY negative edge, then what are the negative edges doing there in the first place? But, this doesn't hold very well, because - outside of hindsight - how would you ever know if a graph could or could not be traversed without going across a negative edge?

Also worth noting, according to the wikipedia page for Djikstra's algorithm :

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

So, even though this conversation is useful and thought provoking; maybe the title of the question should be "What is the proper algorithm to use for traversing a graph with negative edges?" Djikstra's algorithm was intended to find the shortest path. But, if you introduce positive and negative weights, then doesn't the goal change from finding the shortest path to finding the MOST positive - regardless of how many edges are on your chosen path? And if it does, what is your exit condition? The only way you could know you've reached the optimal solution would be if you happened across a path that included all positive edges without any negative edges - and wouldn't this scenario only occur by chance? So - if introducing a situation where there are positive and negative weights changes the goal to be the most positive (or negative depending on how you want to frame it) wouldn't this problem be doomed to O(n!) and therefor be best solved by a decision making algorithm (like alpha/beta) which would produce the best outcome given a restriction on the total amount of edges you're allowed to take?

Upvotes: 1

Derek Ledbetter
Derek Ledbetter

Reputation: 4895

Suppose that walking a distance takes a certain amount of food. But along some paths there is food you can gather, so you might gain food by following those paths.

Upvotes: 13

Will A
Will A

Reputation: 24988

I guess you might get negative weights where you've already got a system with non-negative weights and a path comes along that is cheaper than all existing paths, and for some reason it's expensive to reweight the network.

Upvotes: 1

Nik
Nik

Reputation: 7273

When doing routing, a negative weight might be assigned to a link to make it the default path. You could use this if you have a primary and a backup line and for whatever reason you don't want to load balance between them.

Upvotes: 2

Tom Anderson
Tom Anderson

Reputation: 47183

If you're trying to find the quickest way to swim across a series of linked pools in a water park, and it has flumes.

Upvotes: 0

Related Questions