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).
http://en.wikipedia.org/wiki/Dijkstra's_algorithm your teacher is right
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 :)
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 :)
russian interface
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.