Dijkstra's Algorithm, Hands-On: Shortest Paths

The Story That Explains Dijkstra

Dijkstra's algorithm finds the shortest path from one source node to every other node in a weighted graph. It is greedy: at each step it picks the unvisited node with the smallest known distance, "settles" it as final, and uses it to improve its neighbours. The one rule: all edge weights must be non-negative.

Dijkstra explores outward by distance — nearest nodes settle first, like ripples spreading.

The Five Steps

The Graph We'll Use

Six nodes (A–F), source A, with non-negative edge weights. Here is its adjacency list — each node and the neighbours it connects to, with the cost of each edge.

Hands-On: Watch Each Line Run

The heart of the tutorial. Press Play (or Step) and watch the graph come alive: nodes light up as they're picked and settled, edges flash amber while being relaxed and turn green when they join the shortest-path tree, and the distance labels update live. The priority queue and distance table track state, while the exact Python line running lights up on the right.

import heapq
def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    pq = [(0, src)]
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

The Code, Line by Line — "This Line Does That"

Same program as the animation, fully annotated. Each line maps to a job the visualiser highlights.

import heapq

def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}  # every node unknown
    dist[src] = 0                          # source is 0 away from itself
    pq = [(0, src)]                       # min-heap of (distance, node)
    visited = set()                        # settled nodes
    while pq:                              # until nothing left to explore
        d, u = heapq.heappop(pq)           # closest unsettled node
        if u in visited:                    # stale duplicate?
            continue                      # skip it
        visited.add(u)                      # settle u - distance is final
        for v, w in graph[u]:               # look at each neighbour
            if d + w < dist[v]:            # cheaper path found?
                dist[v] = d + w           # relax: update distance
                heapq.heappush(pq, (dist[v], v))  # queue it for later
    return dist                           # shortest distance to every node

Full Working — Step by Step

Here is the complete trace from source A. Each row is one node being settled, the distances it improves, and the queue afterwards. (stale) entries are old queue items that get skipped when popped.

Reconstructing the Actual Path

The version above returns distances. To get the route, also record each node's predecessor, then walk it backwards from the target.

import heapq

def dijkstra_path(graph, src, target):
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}   # who we came from
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                prev[v] = u            # remember the step
                heapq.heappush(pq, (dist[v], v))
    # walk predecessors backwards
    path, node = [], target
    while node is not None:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

Why Non-Negative Weights?

Time & Space Complexity

Benefits

When To Use It — and When Not To

Dijkstra vs Other Path Algorithms

Golden Rules