phantom11's blog

Dijkstra
By phantom11, 13 years ago, In English

Today I had an argument in the viva session with my teacher on the limitations of the Dijkstra algorithm :(
I told that Dijkstra is not applicable if the graph has a negative weight cycle while the teacher says that it is not applicable if it has negative weight edges.That is the graph containing negative weight edges does not compute shortest path correctly even if it does not contain negative weight cycles.
Please anyone clarify my doubt and also give any book or site ,so that I can show it  as a proof to my teacher,(in case I am correct).

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

http://en.wikipedia.org/wiki/Dijkstra's_algorithm your teacher is right

→ Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
http://www.ics.uci.edu/~eppstein/161/960208.html
The first link in google for "dijkstra negative lengths" contains an article with section named "Dijkstra and negative lengths", which has counterexample.
Now you are free to move this post to drafts until I got a lot of minuses :)
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

If you run Dijkstra without any modifications (i.e. process each node at most once), you definitely won't get the right answer with negative weight edges in general. For example, a graph with three nodes A, B, C and w(A->C) = 2, w(A->B) = 3, w(B->C) = -2 will find the shortest path from A to C as distance 2 in one step (A->C) instead of distance 1 in two steps (A->B->C) since you will process C before B.

EDIT: So many responses before me :)

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

there is dijkstra with potentials: if there is no negative cycles in graph, you can modify your graph edges by adding some potential to each node, so that trees of shortest paths will be equal.

look at Johnson's Algorithm. The fact is, if you we are sure about there is no negative cycles, we can use dijsktra instead of bellman-ford. Or i am wrong? I have used this technique for MinCostMaxFlow , but above people says there is counter example?

UPD: Yes, I am wrong. For MinCostMaxFlow it works because usual at first step there is no negative weights, and after each flow push, we update potentials.

→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
If we use Dijkstra on graph with negative weight edges in right way, it turns into Ford and no longer Dijkstra (though it will fail into infinite cycle if there are negative cycles). Dijkstra is used only on graphs with non-negative edges.
→ Reply