Graph Theory37 sections · 1633 units
Open in Course

Path Reconstruction in Dijkstra

Tracking the actual path

Like in BFS, knowing the distance is not enough. You need the path. Use a parent array. When you relax edge (u,v)(u, v): if you update dist[v], also set parent[v] = u.

After Dijkstra finishes, reconstruct by walking backward: n → parent[n] → parent[parent[n]] → ... → 1. Reverse the list to get the path in order. If dist[target] is still infinity, no path exists. Initialize all parent values to 1-1 so you can detect unreachable nodes during reconstruction.