### acash's blog

By acash, history, 7 months ago, ,

we have to find min cost path in a mtrix from top left to bottom right.

Move allowed -> Right,left,Bottom,Up.

I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?

• -8

 » 7 months ago, # |   0 is cost value always non negative?
 » 7 months ago, # |   +3 If you can move in all four directions, you have a graph with cycles and then you can't use dp.
•  » » 7 months ago, # ^ |   0 If the cost values are non negative is it still true that we can't use dp.
•  » » » 7 months ago, # ^ |   +3 Yes. Because what would dp transitions look like? There can be no cycles among them.
•  » » 7 months ago, # ^ |   0 That's how I implemented it can it be more efficient. https://ideone.com/tvKC9r
•  » » » 7 months ago, # ^ |   0 Can anyone tell me what will be the time complexity of my solution ? I am using dijkstra on a matrix (in above soln) ?
•  » » » » 7 months ago, # ^ |   0 Ffs, make a loop over adjacent cells. Don't repeat the same piece of code 4 times.What is the number of states (vertices of a graph)? What is the number of transitions (edges)? And finally, what is the complexity of Dijkstra?