### DJDD01's blog

By DJDD01, 16 months ago, The Problem — Shortest Path Again?

I used Dijkstra's single source shortest path algorithm but it's giving wrong answer for a few nodes on every test case. Is Dijkstra optimal for this question? If not, why?

My submission

Code  Comments (2)
| Write comment?
 » 16 months ago, # | ← Rev. 2 →   Essentially, this doesn't work because Dijkstra's algorithm finds the shortest path in terms of sum of edge weights, but does not care about the number of edges used (which is important in this problem). Here's a counterexample: 4 4 1 3 5 1 2 2 2 3 1 3 4 2 Shortest path to node 3 is the path 1 -> 2 -> 3, giving the value 1*2 + 2*1 = 4. Dijkstra's algorithm would give this as well. However, to node 4, the algorithm would give the path 1 -> 2 -> 3 -> 4, giving a value of 1*2 + 2*1 + 3*2 = 10, which isn't optimal. Optimal path is 1 -> 3 -> 4, which gives the value 1*5 + 2*2 = 9.
•  » » For optimal Path 1->3->4 the cost will be 1*5+3*2=11 which is >9. How will Djikstra's Algorithm fail for node 4?