Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### DJDD01's blog

By DJDD01, 2 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)
 » 2 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.
•  » » Got it. Thanks!