CODEWITHSUNDEEP
dijkstra
prasanga
prasanga

Reputation: 87

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

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

Upvotes: 6

Views: 5310

Answers (3)

tomas789
tomas789

Reputation: 1330

I will give you an counterexample. Consider following graph

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

Suppose you begun in vertex A and you want shortest path to D. Dijkstra's algorithm would do following steps:

  1. Mark A as visited and add vertices B and C to queue
  2. Fetch from queue vertex with minimal distance. It is B
  3. Mark B as visited and add vertex D to queue.
  4. Fetch from queue. Not it is vertex D.
  5. Mark D as visited

Dijkstra says shortest path from A to D has length 2 but it is obviously not true.

Upvotes: 4

Oddthinking
Oddthinking

Reputation: 25292

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.

Edit:

The above claim assumes bidirectional links. If there is no cycles which have an overall negative weight, you do not have a way to loop around forever, being paid.

In such a case, Dijkstra's algorithm may still fail:

Consider two paths:

  • an optimal path that racks up a cost of 100, before crossing the final edge which has a -25 weight, giving a total of 75, and
  • a suboptimal path that has no negatively-weighted edges with a total cost of 90.

Dijkstra's algorithm will investigate the suboptimal path first, and will declare itself finished when it finds it. It will never follow up the subpath that is worse than the first solution found

Upvotes: 15

john_science
john_science

Reputation: 6551

Imagine you had a directed graph in it with a directed cycle, and the total "distance" around that was a negative weight. If on your way from the Start to the End vertex you could pass through that directed cycle, you could simply go around and around the directed cycle an arbitrary number of times.

And that means you could make you path across the graph have an infinitely negative distance (or effectively so).

However, as long as there are no directed cycles around your graph, you could get away with using Dijkstra's Algorithm without anything exploding on you.

All that being said, there if you have a graph with negative weights, you could use the Belman-Ford algorithm. Because of the generality of this algorithm, however, it is a bit slower. The Bellman-Ford algorithm takes O(V·E), where the Dijkstra's takes O(E + VlogV) time

Upvotes: 2

Related Questions