Every Journey Starts with a Graph

We use some form of routing every day, whether through maps, delivery tracking, or estimated arrival times. Billions of people rely on it daily, and while the technology has improved massively over the years, much of it still shares one idea developed more than sixty years ago.

It is part of the invisible infrastructure we rarely think about. We simply open a map and ask which route will get us to our destination the fastest. In this essay, I want to explore where this technology originated and the idea that still forms the foundation of modern route finding.

Dijkstra’s Algorithm

Almost seventy years ago, Edsger W. Dijkstra, a Dutch mathematician and computer scientist, developed a simple solution to a surprisingly complicated problem:

What is the shortest path from one point to another?

His algorithm shows that the shortest route is not always the most obvious one. To solve this problem, Dijkstra represented possible routes as a weighted graph, like the one shown below.

A graph consists of nodes connected by edges. Each edge is assigned a weight, representing the cost of travelling between two nodes. This cost could represent distance, time, fuel consumption, or almost anything else we want to minimise.

But how is a weighted graph similar to a map or navigation system?

Finding the shortest path

Today, we want to take a trip through Norway’s beautiful Bergen. We start at Øvregaten, just above Bryggen, and would like to visit Korskirken.

In this image, you can see a typical map view with our starting point and destination. To turn the map into something an algorithm can understand, we can place a graph on top of it. Intersections and important waypoints become nodes, while the roads connecting them become edges.

Each edge is then assigned a cost. In a simple example, this could represent the exact distance in metres or kilometres between two points. In a real navigation system, the cost could also account for traffic, speed limits, road closures, or the estimated time required to travel along the road.

The algorithm begins at our starting node A, which receives a distance of zero, since we have not travelled anywhere yet. Every other node initially receives a distance of infinity, because no route to it has been discovered. Our goal is now to reach H with the lowest possible total cost.

Before we start, I would like to explain a few important terms so everyone is on the same page:

• Distance: The lowest total cost currently known for reaching a specific node from our starting point.
• Previous: The previous node on the currently shortest known route.
• Visited: Whether a node has already been selected and processed by the algorithm.

The core idea is surprisingly simple: we always continue from the cheapest currently known unvisited node. From there, we check its neighbours and ask whether travelling through our current node gives us a cheaper route than the one we already know.

Step 1: We start at A and discover two possible directions: B with a total cost of 5 and C with a total cost of 21. Since B is currently cheaper to reach, we select it next. We update our table with both newly discovered distances and mark A as visited.

Step 2: From B, we discover D. Reaching it costs another 4, bringing our total distance from A to 9. Since D is now the cheapest unvisited node we know about, we continue from there.

This is already an important part of the algorithm: we are not comparing individual roads in isolation. We always care about the accumulated cost from our starting point.

Step 3: From D, we can reach both C and E. A route to C is already known, but travelling there through D would result in a higher total cost, so we keep the previous route instead.

The route to E, however, is cheaper, giving it a total distance of 15. We therefore update its distance and continue from E, where we discover F with a total cost of 18.

Step 4: From F, we discover both G and our destination H. At first, it looks like we could already finish our journey: H can be reached with a total cost of 38.

But Dijkstra’s algorithm does not stop just because the destination has been discovered.

G can still be reached for only 23, making it the cheaper unvisited node. We therefore visit G first and check whether it might reveal an even better route to our destination.

Step 5: And it does. Travelling from G to H gives us a new total distance of 33, improving the previous route of 38.

We update H one final time. Our destination has now been reached with the shortest distance found by the algorithm.

To reconstruct the actual route, we can follow the Previous values backwards through the graph:

H ← G ← F ← E ← D ← B ← A

Reversing this gives us the route from our starting point to the destination:

A → B → D → E → F → G → H

The total cost of our journey is 33. In a real navigation system, that number could represent something like distance or estimated travel time.

Unlike simply choosing the cheapest road at every intersection, Dijkstra’s algorithm always considers the total cost of the journey from the starting point.

As it moves through the graph, it keeps track of the cheapest routes it currently knows and replaces them whenever it discovers something better. What eventually appears to us as a simple line on a map is the result of repeatedly asking one question:

Is there a cheaper way to get there?

Who was Dijkstra?

Now that we know how the algorithm works, it is worth looking at the person behind it.

Edsger W. Dijkstra was born on May 11, 1930, in Rotterdam, the Netherlands. In 1956, he developed the shortest-path algorithm we just used, which was later published in 1959 in his paper A Note on Two Problems in Connexion with Graphs.

According to Dijkstra himself, the idea came to him in about twenty minutes while sitting on a café terrace in Amsterdam with his fiancée. He deliberately tried to solve the problem without pen and paper. His reasoning was simple: if the solution became too complicated to keep in his head, it was probably too complicated in general.

What started as a thought experiment on a café terrace eventually became one of the most well-known algorithms in computer science.

In 1972, Dijkstra received the ACM Turing Award, widely regarded as the "Nobel Prize of Computer Science", for his fundamental contributions to programming as a scientific discipline.

His work, however, went far beyond shortest paths. Dijkstra made important contributions to structured programming, operating systems, compilers, semaphores, and mutual exclusion. He also wrote the famous 1968 letter Go To Statement Considered Harmful, criticising the widespread use of goto statements and helping shape the way modern programs are structured.

Dijkstra passed away in 2002 at the age of 72 in Nuenen, the Netherlands. By then, his work had already helped shape several areas of computer science, from programming languages and operating systems to the way we think about algorithms themselves.

Why it still matters now

Dijkstra’s shortest-path algorithm did not disappear as computers became faster and navigation systems became more advanced. Instead, the problem it helped formalise became even more important.

Modern navigation systems such as Google Maps, Apple Maps, and OpenStreetMap-based routing engines work with road networks that can be represented as enormous weighted graphs. The systems used today are far more sophisticated than Dijkstra’s original algorithm and often rely on specialised or heavily optimised routing techniques, but the fundamental problem remains remarkably similar: given a network of possible routes and their costs, find an efficient path from one point to another.

In some areas, Dijkstra’s algorithm itself is still used directly.

One example can be found in computer networks. OSPF, or Open Shortest Path First, is a routing protocol used to determine how data should travel through a network. Routers build a representation of the network and use Dijkstra’s shortest-path algorithm to calculate efficient routes through it.

Its influence also extends beyond maps and networks. Shortest-path algorithms and techniques derived from the same ideas appear in video games, robotics, logistics, warehouse systems, and route planning. Different problems may require different algorithms, but they often begin with the same abstraction we used in Bergen: turn the environment into nodes, connections, and costs, and then search for the best way through it.

More than sixty years after its invention, Dijkstra’s algorithm remains a good example of how a relatively simple idea can become part of the invisible infrastructure around us.

Conclusion

Maps are opened hundreds of millions of times every day. We enter a destination, a route appears almost instantly, and sometimes we even discover a way to get there quicker. For many of us, that blue line simply looks like a route. Now we know what can exist underneath it.

An idea developed almost seventy years ago, simple enough to explain with a small graph, is still more influential than we might think. The ideas behind Dijkstra’s algorithm continue to appear throughout modern computing. Of course, modern routing systems work with far more information than a simple weighted graph. Traffic jams, ETAs, road closures, and countless other factors require much more sophisticated systems, but the fundamental problem underneath them remains familiar.

Some of the most important technology becomes invisible to us. We notice the interface, but rarely the enormous amount of computation happening within milliseconds underneath it. Simplicity on the surface can hide enormous complexity — but that simplicity is exactly what makes complexity accessible.

Now, when you see that blue line appear on your phone, you know that every one of your journeys started with a graph.