confusion about dijkstra algorithm?

Question

According to the Algorithms book Corman, Dijkstra is applicable for only those graphs whose all edges have non negative weights. Does that mean, if there is any edge with negative weight it will not work for whole of the graph? or Will it not count that negative weight edge? Please indicate which one is right?

Answer 1

Dijkstra algorithm can work on a graph of some negative edges sometimes,like:

A-->B-->C

while w(A, B) = -1 and w(B, C) = -2.

But when there is at least one negative edge, it can't prove to be always right. like:

A-->B-->C-->D
 \         /
  \ _____ /

where w(A, B) = 1, w(B, C) = 3, w(C, D) = -5 ,w(A, D) = 2.

If you choose A as sourcepoint, you will get the length of shortest path from A to D is 2 by Dijkstra algorithm, not -1 in fact.

It is because that Dijkstra algorithm is a greedy algorithm, and its proof procedure of correctness uses that all its edges is non-negative to obtain a contradiction. About its proof procedure, you can look it up at Theorem 24.6 (Correctness of Dijkstra’s algorithm) ,Introduction to Algorithm.