11520

# Dijkstra's and A* Search Algorithms for Pathfinding with Obstacles

This Demonstration finds the shortest path between two green points across a field of black obstacles using either Dijkstra's algorithm or A* search. The process of the search algorithm is shown stepwise, with tiles becoming highlighted as they are scanned. The final path, after the process is complete, is shown in red. You can vary the positions of the starting and end points, the layout of the obstacles and the search algorithm.

### DETAILS

This problem is illustrated on a array, with one green cell specified as the start, another as the end, and other black cells occupied by inaccessible obstacles. Movement is allowed in the four cardinal directions as well as diagonally, except past sharp corners of obstacles. The shortest path is found by converting this array to a graph with one vertex for each node of the array, with vertices adjacent if the corresponding tiles are adjacent. Edge costs correspond to Euclidean distance, with a cost of for taking one step in a cardinal direction and for taking a diagonal step.
The two search algorithms, Dijkstra's algorithm and A* search, are common algorithms used for finding shortest paths on a graph (see [1] for detailed descriptions of both).
Dijkstra's algorithm is an iterative process that attempts to find the shortest path from a start vertex to every other vertex. It has been modified in this Demonstration to halt early if it finds the finish vertex. It maintains a list of permanent distances for some vertices and tentative distances for others. Each iteration consists of making one tentative distance permanent and then calculating tentative distances for all neighbors of the new permanent vertex. The animation produced displays the permanent set as dark blue, the tentative set as light blue and the unvisited set as white.
A* search is a modified version of Dijkstra's algorithm. It is a directed search that uses a distance heuristic to preferentially select vertices likely to be closer to the finish vertex. In this case, that heuristic is the Euclidean distance from each vertex to the finish vertex. In general, A* does a good job of moving directly toward the finish over an open area, but because the heuristic does not take obstacles into account, it may take longer to navigate around them.
Reference
[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Englewood Cliffs, NJ: Prentice Hall, 1993.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.