Pathfinding Algorithms
How does a navigation app find the shortest route?
Summary
To find the best route between two points on a map, a computer spreads out step by step from the start to neighbouring points and keeps track of where it has looked. Breadth-first search spreads ring by ring, Dijkstra picks the cheapest point at every step, and A* guesses the direction of the goal so it looks at far fewer places. The same idea is used in navigation apps, in games and in the routes data packets take across the internet.
In depth
Pathfinding is a search problem on a "graph": points (junctions, grid cells) and the links between them (roads). Breadth-first search (BFS) finds the route with the fewest steps but counts every step as equal. The algorithm Edsger Dijkstra found in 1956 takes the different costs of the links (distance, time, traffic) into account and guarantees the cheapest route. A*, developed in 1968 by Hart, Nilsson and Raphael, adds to Dijkstra an estimate of the distance left to the goal; as long as the estimate never exceeds the truth, it still finds the cheapest route while looking at far fewer points. Depth-first and greedy search can be quick but do not guarantee the best route.
Rate Pathfinding Algorithms
What did you think of this content? Click the stars to leave your rating.
Leave a Comment and Rating
Sign in to comment and rate. Membership is free.