Shortest path reconstruction with parent lists in Python

Why it matters

A distance tells you how far a place is. It does not tell you the way there. A map app that says "14 minutes" is only half useful if it cannot also draw the route. Delivery routing, game characters walking around walls and network packets choosing a path all need the route itself, not only its cost.

The fix is simple. While the search runs, every vertex remembers which vertex it was reached from. A vertex is a point in the graph, such as a town or a junction. The memory is called a parent list: a list where index v holds the parent of vertex v. After the search, you start at the target, follow the parents back to the start, and reverse the list. That list is the route.

This lesson uses two searches. Breadth-first search (BFS) finds the route with the fewest edges. Dijkstra's algorithm finds the route with the lowest total weight, where each edge has a number such as a distance or a time. The all-pairs search in the next lesson, Floyd-Warshall, works differently and is covered there.

The idea: breadcrumbs

Imagine you walk through a town and leave a note at each junction. The note says which junction you came from. Later you want to go home. You read the note at your current junction, walk to the place it names, read that note, and repeat until you reach the start. The notes give you the route in reverse.

In Python, the notes are a list named parent. If parent[3] is 1, then vertex 3 was first reached from vertex 1. The start vertex has no parent, so we store -1 there. We also fill the whole list with -1 before the search, using [-1] * n. If we left the list at zeros, the start vertex 0 would have parent 0. The walk back would then never reach -1, and the loop would never stop.

Two terms are used below:

Edge: a line between two vertices. In this lesson an edge can be used in both directions.
Hop: one step along one edge. A route with three edges has three hops.

Example 1: BFS with a parent list

Here is a graph with six vertices, numbered 0 to 5. Vertex 5 has no edges, so no route can reach it.

0 - 1
0 - 2
1 - 3
2 - 3
3 - 4
5 (no edges)

BFS uses a queue, which is a line where the first item added is the first item taken out. It starts at the source, which is vertex 0. Each time it takes a vertex out of the queue, it looks at that vertex's neighbours. A neighbour that has not been seen yet gets three things: it is marked as seen, its parent is set to the vertex being looked at, and it joins the back of the queue.

BFS finds each vertex by the fewest hops, because it visits all vertices one hop away before any vertex two hops away. The first parent set for a vertex is therefore its final parent. That is the reason BFS needs no second pass.

The code uses deque from the collections module for the queue. popleft() takes the front item, and append() adds to the back.

Python · editable

Run it and the output is:

parent array: [-1, 0, 0, 1, 3, -1]
path 0 -> 0: [0]
path 0 -> 1: [0, 1]
path 0 -> 2: [0, 2]
path 0 -> 3: [0, 1, 3]
path 0 -> 4: [0, 1, 3, 4]
path 0 -> 5: []

Read the parent list. Index 3 holds 1, so vertex 3 was reached from vertex 1. Index 4 holds 3, so vertex 4 was reached from vertex 3. Index 5 holds -1 and vertex 5 is not the source, so it was never reached.

Look at vertex 3 closely. It has two possible parents, 1 and 2, because both are one hop from 0 and both touch 3. BFS takes vertex 1 out of the queue first, because 1 was added first when vertex 0 was processed. Vertex 1 sees 3 and sets its parent. When vertex 2 is taken out later, 3 is already seen and the parent stays 1. The route [0, 1, 3] is one of two equal routes, and the rule "first to see it wins" picks it.

The function path_to walks from the target up to the source. It adds each vertex to the end of the list, so the walk visits 4, then 3, then 1, then 0, and the list is [4, 3, 1, 0]. path.reverse() then flips the list in place to give [0, 1, 3, 4]. The walk stops when it reads -1, which is the source's parent.

Adding to the front with insert(0, v) would give the same result, but each insert shifts every item already in the list. Appending and reversing once is faster on long routes.

The check at the top of path_to handles unreachable targets. Vertex 5 has parent -1, but it is not the source, so the check returns an empty list. Without this check, the walk would add 5 to the list and stop, and the result [5] would look like a route.

Example 2: Dijkstra with a parent list

BFS counts hops. It does not look at weights. If an edge has weight 4 and a two-edge detour has total weight 3, BFS still takes the direct edge, because it is one hop. Dijkstra's algorithm fixes this.

Dijkstra keeps a distance for each vertex, which is the lowest total weight found so far from the source. At every step it takes out the vertex with the smallest distance. It uses a priority queue, which is a container that always gives back its smallest item first. Python provides this in the heapq module. heapq.heappush adds an item, and heapq.heappop removes the smallest one. The heap compares tuples item by item, so a tuple (distance, vertex) is ordered by distance first.

When Dijkstra looks at an edge from u to v, it asks one question: is the distance to u plus this edge's weight less than the current distance to v? If yes, the route through u is cheaper. The algorithm then sets dist[v] to the new total, sets parent[v] to u, and pushes v onto the heap. This step is called relaxing the edge. The name is standard. It means tightening the stored upper bound on the distance: the old distance is replaced by a smaller one.

The heap can hold an old entry for a vertex after a cheaper one was added. When an old entry is taken out, its distance is larger than the best distance known, so the code skips it. This check is the line if d > dist[u]: continue.

Python has no largest integer, and a missing distance is marked with math.inf, which is a float infinity. Adding a weight to math.inf gives inf again, so an unreachable vertex never looks cheap.

The graph for this example has seven vertices, numbered 0 to 6. Vertex 6 has no edges.

Python · editable

import heapq
import math

def build_graph(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    return adj

def dijkstra(adj, source):
    dist = [math.inf] * len(adj)
    parent = [-1] * len(adj)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            candidate = d + w
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = u
                heapq.heappush(heap, (candidate, v))
    return dist, parent

def path_to(parent, dist, target):
    if dist[target] == math.inf:
        return []
    path = []
    v = target
    while v != -1:
        path.append(v)
        v = parent[v]
    path.reverse()
    return path

n = 7
edges = [
    (0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15),
    (2, 3, 11), (2, 5, 2), (3, 4, 6), (4, 5, 9),
]
adj = build_graph(n, edges)
dist, parent = dijkstra(adj, 0)
print("dist:", dist)
print("parent:", parent)
for target in range(n):
    path = path_to(parent, dist, target)
    if not path:
        print(f"0 -> {target}: unreachable")
    else:
        print(f"0 -> {target}: {path} cost {dist[target]}")

The output is:

dist: [0, 7, 9, 20, 20, 11, inf]
parent: [-1, 0, 0, 2, 5, 2, -1]
0 -> 0: [0] cost 0
0 -> 1: [0, 1] cost 7
0 -> 2: [0, 2] cost 9
0 -> 3: [0, 2, 3] cost 20
0 -> 4: [0, 2, 5, 4] cost 20
0 -> 5: [0, 2, 5] cost 11
0 -> 6: unreachable

The value inf is math.inf, the code's marker for "no route found yet". A vertex still holding this value after the search cannot be reached.

Check the route to vertex 4. Its parent is 5, which has parent 2, which has parent 0. So the route is 0, 2, 5, 4. The costs add up: 0 to 2 is 9, 2 to 5 is 2, and 5 to 4 is 9. The total is 20. The direct route through vertex 5 from the start costs 14 + 9 = 23, which is more, so it was not chosen.

Notice that the code checks dist for unreachable vertices, not parent. The start vertex and an unreachable vertex both have parent -1. Only the distance tells them apart.

Example 3: a parent can change during the search

In Example 2, a vertex's parent might change after it was first set. Here is a small graph where this happens twice. It has four vertices. The start is vertex 0.

Edges: 0 to 1 with weight 4, 0 to 2 with weight 1, 2 to 1 with weight 2, 1 to 3 with weight 5, and 2 to 3 with weight 8.

The program below is Dijkstra with one extra print line each time a distance improves. It shows the order of events.

Python · editable

The output is:

pop 0 with dist 0
  improve 1: dist inf -> 4, parent -1 -> 0
  improve 2: dist inf -> 1, parent -1 -> 0
pop 2 with dist 1
  improve 1: dist 4 -> 3, parent 0 -> 2
  improve 3: dist inf -> 9, parent -1 -> 2
pop 1 with dist 3
  improve 3: dist 9 -> 8, parent 2 -> 1
pop 3 with dist 8
final parent: [-1, 2, 0, 1]
final dist: [0, 3, 1, 8]

Follow vertex 1. The first route to it is the direct edge from 0, with cost 4, so its parent is 0. Later, the route 0 to 2 to 1 costs 1 + 2 = 3. That is cheaper, so the parent changes to 2. The parent of 1 was not final when it was first set. It became final only when the search had no cheaper route left.

Follow vertex 3. The first route is 0 to 2 to 3, with cost 1 + 8 = 9, so its parent is 2. Then 0 to 2 to 1 to 3 costs 3 + 5 = 8. That changes the parent to 1. The final route is 0, 2, 1, 3, with cost 8. The direct-looking route 0, 2, 3 is 9 and the route 0, 1, 3 is 9, so neither of them wins.

The rule is simple. Each time a cheaper distance is found, the parent is replaced too. The parent list always describes the cheapest route found so far, and once the search ends, that route is the cheapest.

Common mistakes

Printing the route in the wrong order. If the walk adds each vertex to the list and never calls reverse(), the list runs from the target back to the source. For target 3 in Example 1, the walk adds 3, then 1, then 0. No error is shown. The route is simply backwards:

parent = [-1, 0, 0, 1, 3, -1]
path = []
v = 3
while v != -1:
    path.append(v)
    v = parent[v]
print(path)

[3, 1, 0]

Call path.reverse() before you return the list.

Printing a path for an unreachable target. Vertex 5 in Example 1 has parent -1. Without the check at the top of path_to, the walk adds 5, sees -1, and stops:

parent = [-1, 0, 0, 1, 3, -1]
path = []
v = 5
while v != -1:
    path.append(v)
    v = parent[v]
print(path)

[5]

The result [5] looks like a route of zero hops. The check target != source and parent[target] == -1 prevents this.

Leaving the parent list at zeros. A list made with [0] * n holds zeros. If the start vertex keeps parent 0, the walk goes 0, 0, 0 and never reaches -1. Python does not stop the loop by itself. The list grows until the program runs out of memory. The next code stops after five steps so that you can see the repeated zeros:

zero_parent = [0, 0, 0, 1, 3]
steps = []
v = 4
for _ in range(5):
    steps.append(v)
    v = zero_parent[v]
print(steps)

[4, 3, 1, 0, 0]

Always fill the list with -1 before the search, using [-1] * n.

Writing the rebuild as a recursive function without a stop. A recursive function calls itself with the parent of the current vertex. The base case is the point where it must stop. Here is a version with no base case:

def build(parent, v):
    path = build(parent, parent[v])
    path.append(v)
    return path
 
 
print(build([-1, 0, 0, 1, 3], 4))

This does not fail on the first step. It fails when the walk reaches the source. The source's parent is -1, and Python reads parent[-1] as the last item of the list, which is 3, not as an error. So the calls go round the same loop of vertices, 3, 1, 0, -1, 3, and so on, until Python stops the program. The output ends like this, with the middle lines shortened:

Traceback (most recent call last):
  File "...", line 7, in <module>
    print(build([-1, 0, 0, 1, 3], 4))
  File "...", line 2, in build
    path = build(parent, parent[v])
  File "...", line 2, in build
    path = build(parent, parent[v])
  File "...", line 2, in build
    path = build(parent, parent[v])
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

RecursionError means the function called itself more times than Python allows. Python has a limit on how deep the calls may go, and the limit is a number the program can read with sys.getrecursionlimit(). The exact count in the message can differ between Python versions and machines.

The fix is a base case. When v is -1, return an empty list. The fixed version prints the route:

Python · editable

[0, 1, 3, 4]

The loop version in Example 1 avoids the problem because its while v != -1 condition stops at -1 by design.

Using BFS on a weighted graph. BFS gives the route with the fewest hops, not the lowest weight. Take the graph from Example 3 and a search that only uses BFS order. It reaches vertex 1 directly from vertex 0, so the cost is 4. The cheaper route 0, 2, 1 costs 3. The Dijkstra trace above shows the cost of 3 for vertex 1. Use Dijkstra when edges have different weights.

Expecting an overflow on the unreachable marker. In Java, the marker for "no route yet" is the largest long value, and adding a weight to it can wrap around to a negative number. Python integers have no largest value, so a sum never wraps, and math.inf stays infinite when you add to it:

Python · editable

inf
1267650600228229401496703205376

The check if dist[target] == math.inf still matters, because it is what turns an unreachable vertex into an empty route.

Practice

Exercise 1. The parent list for source 0 is [-1, 0, 0, 2, 1]. What is the route from 0 to 3?

Show the answer

Vertex 3 has parent 2. Vertex 2 has parent 0. Vertex 0 is the source. The route is [0, 2, 3].

Exercise 2. For the graph in Example 1, which route does path_to return for target 4 if the edges 1 to 3 and 2 to 3 are both removed?

Show the answer

Vertex 4 is connected only to vertex 3, and vertex 3 now has no edges to 1 or 2. Nothing reaches vertex 3 from vertex 0, so vertex 3 keeps parent -1 and vertex 4 is never reached and keeps parent -1. The function returns an empty list.

Exercise 3. In the trace in Example 3, which vertices change their parent after they were first set, and what are the old and new parents?

Show the answer

Vertex 1 changes from parent 0 to parent 2 when the cost drops from 4 to 3. Vertex 3 changes from parent 2 to parent 1 when the cost drops from 9 to 8. Both changes happen after the vertex was first given a parent.

Exercise 4. Change the BFS code in Example 1 so it also records how many hops each vertex is from the source. Where does the new line go?

Show the answer

Add a list hops of size n, filled with -1 using [-1] * n. Set hops[source] = 0 before the loop. Inside the loop, next to parent[v] = u, add hops[v] = hops[u] + 1. The line goes there because a vertex is first reached by the fewest hops, so the first value set is the correct one.

Exercise 5. For the graph in Example 2, what is the route from 0 to 5 and what is its cost? Why is the route through 2 chosen over the direct edge?

Show the answer

The route is [0, 2, 5] with cost 11. The direct edge from 0 to 5 has weight 14, and the route through 2 costs 9 + 2 = 11. Eleven is less than fourteen, so the search sets the parent of 5 to 2.

Summary

A parent list stores, for each vertex, the vertex it was reached from, with -1 for the source and for unreachable vertices.
To rebuild a route, start at the target, follow parents until -1, and reverse the list.
BFS sets each parent once, because it finds vertices by the fewest hops.
Dijkstra replaces a parent each time it finds a cheaper distance, so the parent is final only at the end.
Check the distance, not the parent, to tell an unreachable vertex from the source when the source's parent is also -1.

Shortest path reconstruction with parent lists in Python

Why it matters

The idea: breadcrumbs

Example 1: BFS with a parent list

Example 2: Dijkstra with a parent list

Example 3: a parent can change during the search

Common mistakes

Practice

Summary

Stuck? Ask the tutor