Блог пользователя phantom11

Dijkstra
Автор phantom11, 13 лет назад, По-английски

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).

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
13 лет назад, # |
← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
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 :)
→ Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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 :)

→ Ответить
»
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

russian interface

→ Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
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.
→ Ответить