Does Dijkstra's algorithm give shortest path always?
dijkstra, graph
Solution
Yes Dijkstra's always gives shortest path when the edge costs are all positive. However, it can fail when there are negative edge costs.
Problem
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.