Dijkstra's algorithm in Python: shortest paths with a heap in O((V + E) log V)

Short answer. Dijkstra's algorithm finds the shortest path from one node to every other node. Edge weights must be non-negative. It pops the closest open node from a heap and relaxes its neighbours. Time O((V + E) log V). Below: the trigger words, Python code, a traced run and Network Delay Time.

What does Dijkstra's algorithm do?

You have a graph where every edge has a weight. You want the cheapest route from the start to each other node.

Breadth-first search counts edges. It only works when every edge costs the same. Dijkstra handles weights, as long as none is negative.

The idea: always take the closest node not yet settled. Its distance cannot improve any more. Use it to improve its neighbours. That improvement step is called relaxing an edge.

When does a problem need Dijkstra's algorithm?

• "Shortest path", "minimum cost", "minimum time".
• "Weighted graph" with non-negative weights.
• "Grid where each cell has an entry cost."
• "How long until a signal reaches every node."

All weights equal to one: use BFS. Negative weights: use Bellman-Ford. Dijkstra sits between the two.

How does the algorithm work step by step?

• Distance to the start is 0, to everything else infinity.
• Push (0, start) onto a min-heap.
• Pop the pair with the smallest distance. If it is larger than the known distance, skip it.
• For each neighbour compute a new distance. If it is smaller than the stored one, store it and push.
• Heap empty: all distances are final.

The skip step is lazy deletion. Stale pairs stay in the heap and get ignored when they surface.

What does one run of Dijkstra's algorithm look like?

Nodes A, B, C, D. Edges: A-B weight 1, A-C weight 4. Also B-C weight 2 and C-D weight 1. Start at A.

Pop A at 0. B becomes 1, C becomes 4. Pop B at 1. Through B, C becomes 3, better than 4, update. Pop C at 3. D becomes 4. Pop the stale (4, C) and skip it. Pop D. Result: A 0, B 1, C 3, D 4.

How do you write Dijkstra's algorithm in Python?

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbour, weight), ...]}
    dist = {v: float("inf") for v in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, v = heapq.heappop(heap)
        if d > dist[v]:
            continue                  # stale entry
        for u, w in graph[v]:
            nd = d + w
            if nd < dist[u]:
                dist[u] = nd
                heapq.heappush(heap, (nd, u))
    return dist

To recover the path itself, keep a prev dictionary. On every improvement set prev[u] = v. Then walk back from the target.

How does Dijkstra compare with its neighbours?

Algorithm	Weights	Time	Use when
BFS	All equal	O(V + E)	Step counts, mazes
Dijkstra	Non-negative	O((V + E) log V)	Roads, delays, prices
Bellman-Ford	Any	O(V · E)	Negative edges exist
Floyd-Warshall	Any	O(V³)	All pairs, small graph

How does it solve Network Delay Time?

You get n nodes, a source, and edges as (from, to, time). Return the time for a signal to reach every node.

Build an adjacency list, run Dijkstra from the source. The answer is the largest distance. If any distance is still infinity, return -1.

What mistakes break a Dijkstra solution?

• Running it on negative weights. The answer is silently wrong.
• Not skipping stale pairs. Still correct, just slower.
• Pushing (node, distance) instead of (distance, node). The heap sorts on the first field.
• Marking a node settled on push instead of on pop.

How do you explain Dijkstra's algorithm in an interview?

Say: weighted graph, non-negative weights, single source. Name the heap and the greedy pick of the closest node. Give O((V + E) log V).

Then justify the greed. Weights are non-negative. No detour can reach the closest node more cheaply. That is the follow-up question almost every time.

Drill the pattern against its neighbours on the Dijkstra's algorithm page. The unweighted case is on the graph BFS / DFS page.

FAQ

Why does Dijkstra fail with negative weights?

A settled node is treated as final. A negative edge could later shorten the path to it. The algorithm never looks again.

Where does Dijkstra show up in real systems?

Map navigation: junctions are nodes, roads are edges, weights are travel times. Network routing protocols such as OSPF run it on every router. Any planner where an action has a cost.

Do I need a visited set?

No. The check d > dist[v] does the same job. A set is fine for clarity, the result is identical.

How do you run it on a grid with cell costs?

Each cell is a node, its four neighbours are edges. The weight is the cost of the cell you enter. Same code.