DJDD01's blog

By DJDD01, 2 years ago, In English

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
  • Vote: I like it
  • +17
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.