Content deleted Content added
Kevin Gorman (talk | contribs) m Reverted edit(s) by 67.255.78.140 identified as probably inappropriate external link using STiki |
→Shortest path algorithm: Rm period from caption |
||
Line 42:
== Shortest path algorithm ==
[[File:MAZE 40x20 DFS no deadends.png|thumb|A maze with many solutions and no dead-ends, where it may be useful to find the shortest path
When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. This algorithm finds 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.
| |||