CODEWITHSUNDEEP
c#.net
Zoltán Raffai
Zoltán Raffai

Reputation: 141

Matrix shortest path with jumping points

I have a random Matrix eg.:

3  A  6  8
9  2  7* 1
6  6  9  1
2  #3 4  B

I need to find, the shortest path from A to B. The * and # marks are jumping points. If you stay on the * marked number, you can jump to the # marked number.

I thought a lot around this, but can't solve. How can i achive this?

Upvotes: 3

Views: 210

Answers (1)

Nitram
Nitram

Reputation: 6716

In case the values in your matrix are the movement cost of one field to another, the algorithm you need is A*. Wikipedia offers you some pseudo code to get started, but if you ask Google, you will find loads and loads of example implementation in every language there is.

In case the movement cost if always the same, it is a A* algorithm too, but in that special case it is Dijkstra's algorithm.

A* is basically Dijkstra's algorithm with the addition of considering changing movement costs.

Upvotes: 4

Related Questions