15 Nov 2025
On this page, I want to show you a real-world application of algorithms. If you have ever used a street maps application, you know that it can provide a route from A to B automatically, more or less anywhere in the world. The route is calculated by a graph search algorithm, of which we will explore several here.
Above we see a region of a map from the Open Street Map collection. For the rest of the page we will be using that same region in different settings. By clicking on ↻ you can rotate through a number of regions which will be loaded into this page.
The colourful tiles above can’t be used as input to an algorithm of course, for that we need to break the data down into a graph of roads and intersections, represented by the edges and nodes above. If you compare the panel above with the previous one you can see that they represent the same region in different ways.
The data we are using includes information about oneway streets as well as bi-directional streets. While we don’t display the directionality here, it is respected by our search algorithms.
The simplest way to find a route in the graph is breadth first search, which is also presented on a separate page on this site. BFS will find the shortest route between two nodes in terms of the minimum number of nodes traversed. But this simply yields the street route with the least number of intersections between start and finish.
On the panel above you can see the start node filled in green and the destination node filled in red. If you click on ▶ to start the animation you can watch BFS finding a route by exploring the nodes through the graph. This is an uninformed search, meaning it does not take geometric information or such into account, it only goes by nodes and edges of the graph.
The software used to make these plots allows us to lay layers of map information above each other. With minimal change, the search nodes of the previous panel can be layed over the map tiles from the top of the page. Note how well roads and intersections match up with the vector data.
Where BFS defines the shortest route by the number of nodes, Dijkstra’s algorithm searches for the shortest route in terms of distance on the ground. For this every edge in the vector data comes with a length in meters. When choosing the next node to explore, Dijkstra’s picks nodes by the running sum of distance from the origin node. This leads to a subtle change in search pattern, which can be seen on these previous panels. Note that this is still all uninformed search.
To further improve the performance of street map search, we turn to an informed search: the legendary A* algorithm. It uses a heuristic to estimate which nodes to explore next to hone in on the target node. Here we have used a simple but effective heuristic, the air line distance between the current node and the target. While real transport can’t take the shortest line, it helps the algorithm move in the right direction. If you run this panel you should see that the route it finds is the same as with the panel on Dijkstra’s algorithm. Both algorithms are optimal like this. A* is just more efficient.
Real street map search code is much more sophisticated than what we have seen on this page, but I hope you get the general idea of what it is about and how data and algorithms work together to yield useful information.
Thank you to the Open Street Map contributors and the OpenLayers team! More content can be found on our main page.