Dijkstra’s Algorithm: The 20-Minute Masterpiece

A Cafe, a Fiancée, and No Paper

In the summer of 1956, a young Dutch computer scientist named Edsger W. Dijkstra was sitting at a café terrace in Amsterdam with his fiancée. He was facing a challenge: to demonstrate the power of a new computer called the ARMAC, he needed to find the shortest route between Rotterdam and Groningen.

The legend says he designed the entire algorithm in just 20 minutes.

Crucially, he had no paper or pen. This constraint forced him to keep the logic so simple and elegant that he could hold it entirely in his mind without making a single mistake. He avoided complex math because he wanted to explain to non-mathematicians how a machine “thinks” about distance.

Dijkstra’s insight was that the most resilient solutions are often the simplest. Today, every time you open Google Maps or send a packet across the internet, you are using those 20 minutes of “paperless” inspiration.

Why do we need it?

Imagine you are building a navigation app. In your world, “distance” isn’t just kilometers—it’s time or cost.

• Highway: 10km takes 5 mins (Cost = 5).
• City Road: 2km takes 10 mins (Cost = 10).

A simple search would pick the City Road because it’s “only one hop.” But you want the fastest route. You need an algorithm that respects the “weight” of each road.

How the Algorithm “Thinks”

The way Dijkstra’s algorithm works is actually quite “stubborn.”

At the start, it is humble and knows nothing about the world:

• It marks the starting point’s distance as 0;
• It marks every other destination as “Unreachable” ($\infty$).

Then, it begins a repetitive, focused journey. In every step, it performs the same ritual:

It looks around and picks the closest node it has seen so far that hasn’t been “finalized” yet. Once it picks a node, the algorithm makes a solemn declaration:

“To get here, there is officially no shorter way possible.”

Only after this declaration does it tentatively lean over to the node’s neighbors and ask:

“If I take one more step from here to you, will you be closer to the start than the path I recorded for you earlier?”

If the answer is yes, it unhesitatingly updates its records. It repeats this process—pick the closest, update the neighbors—until every node has been visited or the destination is reached.

The Logic of the “Now”

In every single step, the algorithm only cares about one thing: Which move has the lowest cost right now?

It never looks back to reconsider a finalized decision, and it doesn’t try to guess the future. This strategy of choosing the immediate best option is known in the world of computer science as a Greedy Algorithm.

Engineering Context: Why it wins in production

In academic papers, we talk about complexity: $O(E \log V)$. But in the real world, engineers choose Dijkstra for its “Cost-Effectiveness.”

By using a Min-Priority Queue, the algorithm’s performance is robust enough to handle:

• City-scale road networks.
• Medium-sized microservice dependency graphs.
• Real-time routing for logistics.

It isn’t the “smartest” algorithm (that would be A*), but its lack of complex heuristics makes it incredibly reliable and easy to debug. It is the “Workhorse” that the industry trusts.

Implementation (Python)

import heapq

def dijkstra(graph, start):
    # 1. Init: Everyone is unreachable except the start
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Priority Queue stores: (distance, node_id)
    # Python's heapq always maintains a Min-Heap
    pq = [(0, start)]

    while pq:
        current_dist, u = heapq.heappop(pq)

        # Stale entry check: if we already found a shorter way, ignore this
        if current_dist > distances[u]:
            continue

        # Explore neighbors
        for v, weight in graph[u].items():
            distance = current_dist + weight
            
            # Tentatively asking: can we do better?
            if distance < distances[v]:
                distances[v] = distance
                heapq.heappush(pq, (distance, v))

    return distances

# Example Usage:
# graph = {'A': {'B': 5, 'C': 10}, 'B': {'C': 3}, 'C': {}}
# print(dijkstra(graph, 'A'))

Summary

Back to that cafe in 1956. No blackboard, no formulas, not even a napkin. Just an engineer asking himself:

“If I can only remember one thing at a time, how do I find the way?”

The answer Dijkstra found was so simple it was almost impossible to be wrong. And that is why, seventy years later, the world still follows his lead.