Shortest Path Algorithm
When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. One possible algorithm finds the shortest path by implementing a breadth-first search, while another, the A* algorithm, uses a heuristic technique. The breadth-first search algorithm uses a 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.
Read more about this topic: Maze Solving Algorithm
Famous quotes containing the words shortest and/or path:
“The Gettysburg speech is at once the shortest and the most famous oration in American history. Put beside it, all the whoopings of the Websters, Sumners and Everetts seem gaudy and silly. It is eloquence brought to a pellucid and almost gem-like perfection—the highest emotion reduced to a few poetical phrases.”
—H.L. (Henry Lewis)
“The living language is like a cowpath: it is the creation of the cows themselves, who, having created it, follow it or depart from it according to their whims or their needs. From daily use, the path undergoes change. A cow is under no obligation to stay in the narrow path she helped make, following the contour of the land, but she often profits by staying with it and she would be handicapped if she didn’t know where it was or where it led to.”
—E.B. (Elwyn Brooks)