Dijkstra's algorithm explained: how it works, code and complexity

What problem Dijkstra's algorithm solves

Breadth-first search finds the path with the fewest edges, but roads, network links and flights have different lengths, costs or delays. Dijkstra's algorithm solves the single-source shortest path problem on such weighted graphs: given a start node, find the cheapest total cost to reach every other node, and the path that achieves it.

Edsger W. Dijkstra published the algorithm in 1959 in the paper "A note on two problems in connexion with graphs".

The idea in plain words

1. Set the distance of the start node to 0 and every other distance to infinity.
2. Pick the unfinished node with the smallest distance. Its distance is now final.
3. Relax each outgoing edge u → v with weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w and remember u as the parent of v.
4. Repeat steps 2 and 3 until every reachable node is finished.

Why is the smallest distance final? Every other route to that node would have to pass through a node whose distance is already at least as large, and with non-negative weights the remaining edges can only add cost.

Worked example, step by step

Directed graph with edges A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3). Start at A.

B first gets distance 4 from the direct edge, then improves to 3 through C. The shortest path to E is A → C → B → D → E with total cost 1 + 2 + 1 + 3 = 7.

Python implementation with heapq

Python's heapq module provides a binary min-heap. Instead of a "decrease key" operation, push a new (distance, node) pair whenever a distance improves and skip outdated pairs when they are popped. This is called lazy deletion.

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

To get the path to one target, follow the parent links back to the start:

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

If you only need the distance to one target, you can stop as soon as that target is popped from the heap: its distance is final at that moment.

Time and space complexity

Space is O(V + E) for the graph, the distance and parent maps, and the heap.

Variants and common mistakes

• Forgetting the if d > dist[u]: continue check is not wrong, but it makes the algorithm process stale entries and can slow it down a lot.
• Pushing only the node instead of (distance, node) makes the heap order meaningless.
• If nodes are objects that cannot be compared, ties in distance make heapq compare the nodes and raise TypeError. Push (distance, counter, node) with a unique counter.
• A* search is Dijkstra with a heuristic added to the priority; it explores fewer nodes when you have a good estimate of the remaining distance.
• Bidirectional Dijkstra runs from both the start and the goal and stops when the searches meet.

When to use it and real-world uses

• Routing: link-state routing protocols such as OSPF and IS-IS run a shortest path first computation based on Dijkstra's algorithm.
• Maps and navigation, where production systems add preprocessing on top of Dijkstra-style search.
• Interview problems: network delay time, cheapest flights (with a stop limit), path with minimum effort in a grid, and any "minimum total cost" question on a graph.