vaibnak7's blog

Can it be solved by dijkshtra algorithm ?
By vaibnak7, history, 3 years ago, In English

I came across the following problem :

There is an array of size n and you are currently located at the starting point of the array, you want to go to the ending point of the array by only using steps of +3 and -1.

like if you are at x you can either go to x+3 or x-1.

The total cost of this work will be equal to the sum of the values at the indices you go through to reach the end of the array. Find the minimum cost incurred.

ex.
[4 2 1 5 6]
here the best way is 4 -> 1 -> 2 -> 6
cost = 13.

size of array <= 1e3
1 <= a[i] <= 1e3

Approach :

There is a DP solution for this problem, but I was wondering can it be solved by dijkshtra algorithm where we assume that index x is connect to index x+3 and x-1, taking source as 0th index and target as (n-1)th index. The magnitude of edges being the value of the node it is leading to.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vaibnak7 (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You just transposed this problem into standard dijkstra's algorithm problem, what makes you think it will not work?

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

There is a DP solution for this problem

Are you referring to: dp[i] = min cost to get to index i? (And transition: dp[i] = a[i] + min(dp[i-3], dp[i+1]))

If you tried this dp, iterating from i= 0 to n-1 wouldn't work as you don't have the property: previous dp states are calculated before the current dp state.

So what order to calculate dp states?

It turns out if we do a Dijkstra's, then the length array (in Dijkstra's) is exactly the above dp array. And the order of nodes we visit in Dijkstra's does have the property: previous dp states are calculated before the current dp state.

So the Dijkstra's and the dp solution are really the same solution, thought of differently

→ Reply