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.
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.
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.
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.