---
title: "Dijkstra's algorithm in Python: shortest paths with a heap in O((V + E) log V)"
url: https://algopath.pro/blog/dijkstra-algorithm-python
language: en
summary: "How Dijkstra finds shortest paths in a weighted graph, why the greedy pick is safe, Python code with heapq, a traced run, and Network Delay Time."
updated: 2026-10-15
---

# 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](/patterns/dijkstra) page. The unweighted case is on the [graph BFS / DFS](/patterns/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.