Блог пользователя DJDD01

Автор DJDD01, 20 месяцев назад, По-английски

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
  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
20 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?