Path Reconstruction

Path reconstruction records enough information to recover the actual route, not only the shortest distance or best score.

Many graph problems ask for the path itself.

Core Idea

While computing distances or reachability, store a predecessor for each vertex. The predecessor says which previous vertex led to the best known result.

After the algorithm finishes, follow predecessors backward from the target to the start, then reverse the list.

Function Contract

reconstruct_path(parent, start, target) expects a parent dictionary produced during search or shortest-path computation.

parent[node] should be the previous vertex on the chosen path, and parent[start] should usually be None. The function returns a path list from start to target, or None if no parent chain reaches start.

Python Example

def reconstruct_path(parent, start, target):
    path = []
    current = target
 
    while current is not None:
        path.append(current)
        if current == start:
            break
        current = parent.get(current)
 
    if not path or path[-1] != start:
        return None
 
    return path[::-1]

The parent dictionary maps each vertex to the previous vertex on the chosen path.

Recording Parents During Search

In BFS, a parent can be recorded when a node is first discovered:

parent = {start: None}
 
for neighbor in graph[node]:
    if neighbor not in parent:
        parent[neighbor] = node

The parent relation forms a tree of discovered shortest paths in an unweighted graph.

Step-by-Step Example

If the chosen path is:

A -> C -> D

the parent table stores:

parent[D] = C
parent[C] = A
parent[A] = None

Reconstruction starts at D, follows parents backward to A, and reverses the result.

Complexity

Recording parents usually adds O(V) space. Reconstructing one path costs O(length of path).

Common Confusions

Distance is not enough to reconstruct a path. The algorithm must store predecessor information while it still knows how each improvement happened.

If multiple shortest paths exist, the reconstructed path depends on tie-breaking and traversal order.

Another common mistake is overwriting parents carelessly. In shortest path algorithms, update the parent only when the corresponding best distance or discovery state improves.

When To Use It

Use path reconstruction when the required output includes the route, choices, selected items, or sequence of states that produces the optimal value.

Do not add parent tracking if only the numeric distance or count is needed, unless it helps debugging or explanation.

The Main Point

Path reconstruction requires storing predecessor choices while the algorithm still knows how each best result was reached.