Build a Raspberry Pi Pico route finder using Dijkstra's algorithm - Raspberry Pi

We use some essential cookies to make our website work.

We use optional cookies, as detailed in our cookie policy, to remember your<br>settings and understand how you use our website.

Accept optional cookies

Reject optional cookies

News

All news

Search the archive

RSS feed

In the 1950s, Dutch computer scientist Edsger Dijkstra developed a route-finding algorithm so important that, 70 years later, it is still part of the computer science curriculum. In this article, we are going to consider what Dijkstra’s algorithm does, how it works, and discover where it can be used. Along the way, we’ll brush up on some Python programming techniques, find some treasure, and build a pocket route finder using Raspberry Pi Pico.

How does your satnav find your way home? How do networks decide which way to send data packets? How can a robot find its way around an obstacle? The answer to all these questions is by creating a graph of linked data nodes and then using something like Dijkstra’s algorithm to create routing data from the graph.

Dijkstra’s algorithm

Figure 1 shows the Pico Route Finder. It contains map information for locations in the UK and will tell you the distance and the routes between them. Let’s look at how Dijkstra’s algorithm makes it work, starting with how the algorithm came about.

Figure 1: The route finder contains a Raspberry Pi Pico running a MicroPython program

The story is that Dijkstra was having a coffee in Amsterdam and thinking about navigation. In the back of his mind, he was also wondering what he could write to demonstrate a new computer he was working on. After a few minutes of pondering, he came up with his algorithm, which boils down to three rules:

Keep track of how much it costs to go to places

Always use the lowest-cost route first when exploring

Keep track of where you have been

Let’s see how we can use these rules to find the cheapest route to some treasure. Suppose we are visiting a castle, and the owner tells us:

“I want you to chart a path from the Hall to my Treasure Room, where I have placed a pile of gold coins. You can have all the coins in the Treasure Room minus the cost of getting there. Each door on your path has a cost. You can roam the castle as much as you like, but when you have finished you can meet me in the Treasure Room, tell me the path you have devised, and I’ll give you your reward.”

Scores on the doors

We look around the Hall and see three labelled doors, as shown in Figure 2 . The labels say ‘Kitchen: Cost 5’, ‘Library: Cost 2’, ‘Treasure Room: Cost 100’. We could go straight to the Treasure Room, which would cost us 100 coins. Or we could try our luck at finding a cheaper route. Fortunately, we are computer scientists familiar with Dijkstra’s algorithm, so we open our notebook and draw a table. Each door tells us about a new room and the cost of getting there from that room. We enter this information into our table, starting with the Hall, which is where we are now.

Figure 2: You would expect the path to the Treasure Room to be expensive

Figure 3 shows our first table. It describes rooms we know about, whether we have visited them, the cost of getting to each room from the Hall, and the route back to the start of our journey. Dijkstra’s algorithm says that we should now find the lowest-cost unvisited room, travel to that room, and update our table. So, we go to the Library.

Figure 3: We will update the values in the table as we learn more about the paths between rooms

Want gold, will travel

The doors in Figure 4 tell us it costs 2 to reach the Kitchen from the Library and 4 to reach the Armoury. They also tell us that it costs 2 to reach the Hall, but we already knew that from the door in the Hall. We use these numbers to update the table. Let’s start with the Armoury. It costs us 4 to get to the Armoury from the Library, and it costs 2 to get to the Library from the Hall. So, the total cost of getting to the Armoury from the Hall is 6. We add the Armoury to our table and note that the route back to the Hall from the Armoury starts by going to the Library and then going on to the Hall.

Figure 4: We discover new information when we see the routes

Now we can update our table to save us some gold. Dijkstra’s algorithm tells us to keep track of journey costs. If we find a new cost that is less than one in the table, we need to update the table. It cost us 2 to get to the Library and it would cost 2 more to get from the Library to the Kitchen, making a total of 4. The cost of going directly from the Hall to the Kitchen was initially entered as 5 (the cost on the door in the Hall). But if we travel from the Hall to the Kitchen via the Library, we can save a gold coin. We update the table with this new information.

Figure 5 shows our updated table with out-of-date information crossed out. Our next stop will be the unvisited room with the lowest cost, which is...