Course contentsShow
← Computer Science
Lesson 975 of 2,87223. Shortest Path AlgorithmsFree lesson

Path Reconstruction from Predecessor Array

Using the predecessor pointers to reconstruct the actual shortest path from source to any vertex.

Path Reconstruction from Predecessor Array

You'll learn how to use the predecessor pointers created during shortest path algorithms to rebuild the actual path from source to any destination vertex.

The Core Idea

When Dijkstra's algorithm (or similar shortest path algorithms) runs, it tracks how each vertex was reached by storing a predecessor array. For each vertex v, the predecessor pred[v] stores which vertex came immediately before v on the shortest path from the source. Once the algorithm finishes, you can reconstruct the complete path by tracing these pointers backwards from the destination to the source, then reversing the result.

Think of it like breadcrumbs: if you want to retrace your steps from where you are back home, you follow the trail backwards, then flip the directions to get the forward route.

How It Works

  1. Start at your destination vertex dest
  2. Follow predecessors backward: repeatedly jump to pred[dest], then pred[pred[dest]], and so on
  3. Stop when you reach the source (where pred[source] is typically null or -1)
  4. Reverse the collected vertices to get the path from source to destination

For example, if pred[5] = 3, pred[3] = 1, and pred[1] = -1 (meaning 1 is the source), then the path to vertex 5 is [1 → 3 → 5].

Pseudo-Logic (no code yet)

  • Initialize empty path list
  • Current = destination
  • While current is not null/invalid:
    • Add current to path
    • Current = predecessor of current
  • Reverse the path list

Key Takeaway: The predecessor array acts as a reverse roadmap—by walking it backward from any destination and then flipping the sequence, you reconstruct the exact shortest path found by your algorithm.