Maze-solving algorithm: Difference between revisions

Revision as of 17:35, 12 March 2010

Revision as of 03:33, 21 March 2010

Line 42:

== Shortest path algorithm ==

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. This algorithm findfinds the shortest path by implementing a [[breadth-first search]]. The algorithm uses a [[queue (data structure)|queue]] to visit cells in increasing distance order from the start until the finish is reached. Each visited cell needs to keep track of its distance from the start or which adjacent cell nearer to the start caused it to be added to the queue. When the finish ___location is found, follow the path of cells backwards to the start, which is the shortest path.

== References ==