Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to
only vertex $a$
only vertices $a, e, f, g, h$
only vertices $a, b, c, d$
all the vertices
no it does not fail...
e= -2 in 2nd pass and in 7th pass it -1 but -2 is less than -1 so we need not to relax it ..
so it work fine ...
@sushmita, No. 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 increese, 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 )
Will this be the graph with shortest path estimates?
I'm getting below shortest path graph. Is it correct?
@Sachin Mittal, for the graph given by you, isn't following solution work?
Just quickly check for negative edge weight cycle. If no negative edge weight cycle then Dijkstra's algo. will work fine.
If you are not confident in detected cycle( or cycle detection) then simulation of Dijkstra's algo. is done in below image.
can yu just tell how to quickly check for negative edge weight cycle?
Dijkstra algorithm fails when the graph contains negative weight cycle forms . The graph contains only negative weights then the dijkstra gives correct shortest paths from source to every edge. so the answer is D.