# help reqd in path finding algorthms

This topic is 3257 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, Following is my problem: Given is a matrix with a label for each vertex saying it is a "danger spot" or a "safe spot". Also the starting and destination vertex are provided at run time. I need to figure out the quickest route possible with this given input. Any suggestions as to which algorithm I should use?

##### Share on other sites
By a "matrix", I assume you mean you're pathing on a 2D grid? A* is the most commonly used algorithm for this sort of thing.

##### Share on other sites
Or you could also try Dijkstra's Shortest Path algorithm

##### Share on other sites
Quote:
 Or you could also try Dijkstra's Shortest Path algorithm
My understanding is that A* is a variation of Dijkstra. A* incorporates a heuristic, which causes it to perform better than Dijkstra in the general case. However, there are cases where a meaningful heuristic may not be available, in which case Dijkstra is the better choice.

So in other words, A* vs. Dijkstra isn't really a 'six of one, half dozen of the other' choice; they have different characteristics and different uses.

Given the information that the OP provided, it seems pretty clear that A* is the better choice in this case (unless I've overlooked something).

##### Share on other sites
Just figured it would be easier for OP to understand and find a working Dijkstra's then try to get A* working (its just a breadth first search with a heuristic anyway as you point out), but for a beginner DSP might be easier.

1. 1
Rutin
23
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 29
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631740
• Total Posts
3001965
×