Dijkstra's Algorithm Explained Simply (With Python Code)

Let's be honest. When you first hear the name "Dijkstra" in a computer science class or an interview prep session, it sounds intimidating. It sounds like one of those algorithms that require a PhD in mathematics to understand.

But I remember the exact moment it finally clicked for me. I was drawing circles and arrows on a whiteboard, tracing the shortest path to get to my favorite coffee shop, and suddenly, I realized—Dijkstra's algorithm is just a really, really systematic way of finding the quickest route.

It’s the backbone of Google Maps, network routing protocols, and countless coding interview questions. If you can wrap your head around this, graph problems become significantly less scary. So, let’s break it down simply. No complex jargon, just the raw intuition and the Python code to back it up.

The Core Intuition: The Water Metaphor

Imagine a graph of interconnected nodes. You are standing at the starting node with a bucket of water. When you pour the water out, it flows along the edges to the neighboring nodes. But the edges have different lengths (or "weights").

The water will reach the nodes connected by shorter edges before it reaches the nodes connected by longer edges.

Dijkstra’s algorithm does exactly this. It radiates outwards from the starting point, always exploring the closest, cheapest, or shortest unvisited node next. It essentially asks: "Of all the nodes I can currently see, which one is the closest?" It moves there, updates its view of the world, and repeats.

The Three Golden Rules of Dijkstra

Before we look at code, let's establish the rules of the game:

1. Keep track of distances: We need a way to remember the shortest distance from the start node to every other node. We initially set these to infinity (since we haven't explored them yet), except the start node, which is 0.
2. Prioritize the closest: We always want to process the node with the smallest known distance next. (Spoiler alert: A Priority Queue or Min-Heap is perfect for this).
3. Relax the edges: When we visit a node, we look at all its neighbors. If the distance to a neighbor through our current node is shorter than the neighbor's current known distance, we update it. This is called "relaxation."

A technical diagram showing nodes, edges, and the distance weights being calculated.

Why Not Just Use Breadth-First Search (BFS)?

You might be thinking, "Doesn't BFS already find the shortest path?"

Yes, but only if all the edges have the exact same weight (e.g., every step takes 1 minute). The real world isn't like that. Some roads have traffic. Some network links are slower. Dijkstra handles graphs where edges have different non-negative weights.

(Note: If your graph has negative weights, Dijkstra will break. You'll need the Bellman-Ford algorithm for that. But that's a story for another day.)

The Python Implementation

Alright, let's translate this intuition into Python code. We'll use the built-in heapq module to act as our priority queue.

import heapq

def dijkstra(graph, start):
    # Dictionary to track the shortest distance to each node.
    # Initialize all to infinity.
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # Priority queue to hold (distance, node).
    pq = [(0, start)]
    
    while pq:
        # Pop the node with the smallest distance
        current_distance, current_node = heapq.heappop(pq)
        
        # If we've found a shorter path to this node previously, skip it.
        # This is an important optimization!
        if current_distance > distances[current_node]:
            continue
            
        # Check all neighbors of the current node
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # If we found a shorter path to the neighbor, update and push to queue
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances

# Example Usage:
# A graph represented as an adjacency list
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 5, 'D': 10},
    'C': {'E': 3},
    'D': {'F': 11},
    'E': {'D': 4},
    'F': {}
}

print(dijkstra(graph, 'A'))
# Output: {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

Walking Through the Code

Let's dissect the most critical parts:

• heapq.heappop(pq): This is the engine of the algorithm. It guarantees that we are always processing the node that is currently closest to our starting point.
• if current_distance > distances[current_node]: continue: This line handles outdated entries in our priority queue. Sometimes, we find a shorter path to a node after we've already added a longer path to the queue. This check ensures we don't waste time processing the old, longer path.
• The Relaxation Step: if distance < distances[neighbor]: is where the magic happens. We only update a node's distance if we've genuinely found a faster route.

The Time Complexity

In interviews, you must know the time complexity.

With an adjacency list and a priority queue (min-heap), the time complexity is O((V + E) log V), where V is the number of vertices (nodes) and E is the number of edges.

Why? Because in the worst case, we might add every edge to the priority queue. Extracting the minimum from a heap of size V takes O(log V) time. So, doing that for E edges gives us O(E log V).

Final Thoughts

Dijkstra's algorithm is a beautiful piece of computer science history. Once you understand that it's just systematically exploring the closest options first and updating distances when it finds a shortcut, the code practically writes itself.

If you're gearing up for a technical interview and want to practice graph traversal problems like this in a realistic setting, check out totop.app. It’s designed to help you simulate these high-pressure coding scenarios so you can walk into your interview feeling confident, not intimidated. Keep practicing, and those shortest paths will start to look a lot clearer!