Why can't we apply Dijkstra's algorithm for a graph with negative weights?

Question

Why can't we apply Dijkstra's algorithm for a graph with negative weights?

Answer 1

What does it mean to find the least expensive route from A to B if you get paid every time you travel from C to D?

If there is negative weight between the two nodes, the “shortest path” is to cycle back and forth between the two nodes forever. The more jumps, the shorter the path will be.

This is not related to the algorithm, and all this is due to the inability to answer such a question.

Edit

The above claim involves bidirectional links. If there are no cycles that have a common negative weight, you have no way to go in cycles forever by paying.

In this case, Dijkstra's algorithm may still crash:

Consider two ways:

• the optimal path that can withstand a cost of 100 before crossing the end edge, which has -25 weight, giving a total of 75, and
• suboptimal path that does not have negatively weighted edges with a total cost of 90.

The Dijkstra algorithm first explores the suboptimal path and declares itself complete when it finds it. It will never track a subpath that is worse than the first found.

Answer 2

I will give you a counterexample. Consider the following graph

http://img853.imageshack.us/img853/7318/3fk8.png

Suppose you started at the top of A , and you need the shortest path to D Dijkstra's algorithm would perform the following steps:

• Mark A as visited and add the vertices B and C to the queue.
• Extract from the top of the queue with the minimum distance. This is B
• Mark B as visited and add vertex D to the queue.
• Remove from queue. This is not peak D
• Mark D as visited

Dijkstra says that the shortest path from A to D has a length of 2, but this is obviously not the case.

Answer 3

Imagine that a directed graph with a directed cycle was directed in it, and the total "distance" around it was negative. If you can go through this directed cycle on your way from the top of the “Beginning to the End”, you can simply go around the directed cycle an arbitrary number of times.

And that means that you can make the graph path infinitely negative (or efficient).

However, as long as there are no directed loops around your chart, you can avoid using the Dijkstra algorithm without any explosion on you.

All of the above, if you have a chart with negative weights, you can use the Belman-Ford algorithm. However, due to the generality of this algorithm, it is a bit slower. The Bellman-Ford algorithm takes O (V · E), where Dijkstra takes the time O (E + VlogV)