Python · Course navigation

Python Dijkstra shortest paths

Relax nonnegative weighted edges using a priority queue.

On this page

Before you start

Graphs, dictionaries, and heaps.

Relax nonnegative weighted edges using a priority queue.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Dijkstra's algorithm repeatedly processes the smallest tentative distance. Relaxing an edge means replacing a distance when a cheaper route is found.

This implementation permits multiple heap entries for one vertex and skips stale entries. It assumes all edge weights are nonnegative; negative weights invalidate the algorithm's guarantee.

Code example

Python

import heapq

def shortest_paths(graph, start):
    distances = {start: 0}
    heap = [(0, start)]
    while heap:
        distance, node = heapq.heappop(heap)
        if distance != distances[node]:
            continue
        for neighbor, weight in graph.get(node, []):
            if weight < 0:
                raise ValueError("nonnegative weights required")
            candidate = distance + weight
            if candidate < distances.get(neighbor, float("inf")):
                distances[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return distances

graph = {"A": [("B", 4), ("C", 1)], "C": [("B", 2)], "B": []}
result = shortest_paths(graph, "A")
print(sorted(result.items()))
assert shortest_paths({}, "A") == {"A": 0}

Output

[('A', 0), ('B', 3), ('C', 1)]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1import heapq

3def shortest_paths(graph, start):

4 distances = {start: 0}

5 heap = [(0, start)]

6 while heap:

7 distance, node = heapq.heappop(heap)

8 if distance != distances[node]:

9 continue

10 for neighbor, weight in graph.get(node, []):

11 if weight < 0:

12 raise ValueError("nonnegative weights required")

13 candidate = distance + weight

14 if candidate < distances.get(neighbor, float("inf")):

15 distances[neighbor] = candidate

16 heapq.heappush(heap, (candidate, neighbor))

17 return distances

19graph = {"A": [("B", 4), ("C", 1)], "C": [("B", 2)], "B": []}

20result = shortest_paths(graph, "A")

21print(sorted(result.items()))

22assert shortest_paths({}, "A") == {"A": 0}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Start at A with distance zero.	`distances = {A: 0}, heap = [(0,A)]`	—
From A, discover B at 4 and C at 1.	`distances = {A: 0, B: 4, C: 1}`	—
C has the smallest pending distance.	`distance = 1, node = C`	—
The route A-C-B costs 1+2=3, improving B.	`distances = {A: 0, B: 3, C: 1}`	—
Process B at distance 3; it has no outgoing edges.	`distances = {A: 0, B: 3, C: 1}`	—
Later pop the stale B distance 4 and skip it.	`4 != distances[B] (3)`	—
Display distances sorted by vertex name.	`4 != distances[B] (3)`	[('A', 0), ('B', 3), ('C', 1)]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O((V+E) log(E+1)) time and O(V+E) auxiliary space for this lazy-heap version, assuming constant-size numeric operations and average dictionary access.

Unreachable vertices are absent from the returned dictionary.
Equal-distance heap entries require comparable vertex labels here; use a tie-breaker for arbitrary objects.

Try it yourself

Change edge A-B from 4 to 1.

Reveal answer and reasoning

B's shortest distance becomes 1; the route through C costs 3 and does not improve it.