GRAPH WITH ONLY POSITIVE WT: Dijkstra will work fine
GRAPH WITH NEGATIVE WT EDGES BUT NO NEGATIVE WT CYCLE: Dijkstra may or may not fail
GRAPH WITH NEGATIVE WT CYCLE: Dijkstra surely fails
Why Dijstra will work in -ve edges ?.
It may fail in -ve edge even there is no -ve cycle.
Can u calculate distance from A to C using Dijkstra ?, It will be 2, right ?
But actual shortest distance is 1 only. (Here Dijkstra fails even NO cycle.)
Here whats happening, Observe:-
Dijkstra had 2 choices to go to C from A, It chooses direct path.
It says if I go via B, then i would have to incur ATLEAST 5 cost. (it don't know that in future there may be a -ve edge.)
It thinks, A to B distance itself is 5 and if I go via B then cost would always increase, there is no chance of decrease. but to his surprise I put "-4"
Actually Dijkstra assumes that all edges are +ve. (if u see proof of " correctness of Dijkstra" then first assumption is weights are +ve )