Why can't we apply Dijkstra's algorithm for a graph with negative weights?
+8
A:
- Read and understand Dijkstra's algorithm.
- Create a petty graph containing negative weights.
- Test the algorithm.
- Check the result against the one you get by hand.
- ...
- Profit.
Borealid
2010-07-08 03:11:10
This. One hundred times this. Especially the first point.
Anon.
2010-07-08 03:12:19
By the way, I can guarantee that prasanga won't profit from this answer if the steps are followed correctly.
Borealid
2010-07-08 03:26:56
Anon.: I really don't see how it's helpful to reply to someone who clearly doesn't fully understand Dijkstra's algorithm by saying simply "read and understand Dijkstra's algorithm". That's what he's asking! Every question on SO could be answered by "read and understand __". The point of this site is to help people understand, not throw it in their faces.
Ken
2010-07-08 04:14:54
@Ken: there are readily-available algorithmic step-by-step applications of Dijkstra. So, presumably, even without really understanding *why* the algorithm works, one can apply it. If the original poster were to do this on a graph with negative weights, they'd quickly see the algorithm not working, and with a little thought should be able to understand why. I'm not trolling, here.
Borealid
2010-07-08 04:21:55
Borealid: Sure, there are. There's lots of *everything* on the internet. But there's also a reason LMGTFY is banned here. They're trying to build a repository of just such answers here -- all the way down to "what is a variable?" -- and not turn people away simply because they didn't do enough research first.
Ken
2010-07-08 04:50:55
A:
Think about the conditions for terminating the search.
Now, think about what paths in the graph with negative net weight do to that condition.
dmckee
2010-07-08 03:14:48
+8
A:
What does it mean to find the least expensive path from A to B, if every time you travel from C to D you get paid?
If there is a negative weight between two nodes, the "shortest path" is to loop backwards and forwards between those two nodes forever. The more hops, the "shorter" the path gets.
This is nothing to do with the algorithm, and all to do with the impossibility of answering such a question.
Oddthinking
2010-07-08 03:17:55