Python Dijkstra shortest paths

Relax nonnegative weighted edges using a priority queue.

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)]

Explanation

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.

Explore the dry run

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)]

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.

Python Dijkstra shortest paths

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading