Does Dijkstra's algorithm give shortest path always?

Question

I am learning Dijkstra's algorithm and had a basic query. I have a graph that looks as follows..(non-negative nodes):

A---2-----B------16------D-----3-------F
* *
* *
3 4
* *
C----------2---------------------------E

Not clear from above graph display, but AC has a distance of 3 and EF has a distance of 4.

I am interested in finding shortest path between A and F.

Consider destination node F. When we consider its nearest node, we get D (DF has weight 3 and EF 4). However, when we follow that path, we get the shortest path as: A,B,D,F (total distance: 19).

A quick observation tells us that the shortest path is actually A,C,E,F (distance: 9). However, since in the 1st step, E was more distant than D, we followed D.

Am I missing something here? Dijkstra's algorithm is clearly not showing the right result here.

Answer 1

Yes Dijkstra's always gives shortest path when the edge costs are all positive. However, it can fail when there are negative edge costs.