Shortest path reconstruction with parent arrays

Why this matters

A shortest path algorithm answers two questions: how far is it, and which way do I go. Dijkstra and BFS answer the first question directly. They give you a number for each vertex. The second question needs one extra piece of memory, and beginners often miss it. A map app that tells you "12 minutes" but cannot draw the route is not much use.

This lesson adds that memory. You will store, for every vertex, the vertex you arrived from. That single array is enough to rebuild the whole route, one step at a time, from the target back to the start. The lesson uses the weighted version of Dijkstra's algorithm and the grid version of breadth-first search (BFS). Earlier lessons in this module covered the algorithms themselves, and the Floyd-Warshall lesson later in this module covers all pairs at once.

You need vector, queue and priority_queue from the earlier STL work, and the idea of a graph from the first lesson of this module.

A distance is not a route

Start with a small town map. There are six places, A to F, joined by roads. Each road has a length in minutes. You want the fastest way from A to every other place.

The roads are A-B 7, A-C 9, C-F 2, F-E 9, C-D 11 and A-F 14, and each can be used in both directions. Dijkstra's algorithm gives you this table of costs:

The table says that E is 20 minutes away. It does not say how to get there. You need to remember, while the algorithm runs, which road gave each best cost.

A parent array stores one number per vertex

A parent of a vertex is the vertex you came from on the best route found so far. A parent array is a plain array with one slot per vertex. Slot v holds the parent of v. The array is the path memory: you can read it later and walk backwards.

The start vertex has no parent. Its slot holds a marker that means "nobody". This lesson uses -1 and names it with a constant:

constexpr int NONE = -1;

For the town map, the parent array after the search looks like this. Read it as "to reach this place, you come from that place":

To reach E, you come from F. To reach F, you come from C. To reach C, you come from A. Those three links together form the route A -> C -> F -> E. The next sections show how the program turns that chain into a list.

Recording the parent in Dijkstra

Dijkstra's algorithm keeps a distance for each vertex, starting at infinity and the start at 0. When it looks at an edge from v to u, it checks whether going through v gives u a shorter distance. If it does, it updates the distance. The parent update goes in the same place.

The rule is simple: set parent[u] = v only when the distance to u actually improves. If you set it on every look, the parent would point at a route that is longer than the best one.

Here is the full function. It uses a priority_queue that always gives back the closest unfinished vertex. The types go first because the function refers to them:

#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
 
using namespace std;
 
struct Edge {
    int to;
    int weight;
};
 
using Graph = vector<vector<Edge>>;
 
constexpr int NONE = -1;
constexpr long long INF = numeric_limits<long long>::max() / 4;
 
struct ShortestPaths {
    vector<long long> dist;
    vector<int> parent;
};
 
ShortestPaths dijkstra(const Graph& g, int source) {
    int n = static_cast<int>(g.size());
    ShortestPaths r{vector<long long>(n, INF), vector<int>(n, NONE)};
    r.dist[source] = 0;
 
    using Item = pair<long long, int>;  // (distance, vertex)
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    pq.push({0, source});
 
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > r.dist[v]) continue;  // an old, longer entry for v
        for (const Edge& e : g[v]) {
            if (d + e.weight < r.dist[e.to]) {
                r.dist[e.to] = d + e.weight;
                r.parent[e.to] = v;  // remember how we got there
                pq.push({r.dist[e.to], e.to});
            }
        }
    }
    return r;
}

The line if (d > r.dist[v]) continue; needs a comment. The queue can hold the same vertex more than once, once for each time its distance improved. When a vertex comes out of the queue with a distance larger than the best one already known, that entry is old, so the code skips it.

The ShortestPaths struct returns both arrays together. Callers get the costs and the parents from one call.

For the town map, running this function from A and printing each parent gives:

A came from nobody
B came from A
C came from A
D came from C
E came from F
F came from C

Rebuilding the path from the target

The parent array points backwards. To get the route in the normal order, start at the target, write it down, jump to its parent, and repeat. Stop when you reach a vertex with no parent. That vertex is the start. The list you wrote is backwards, so reverse it at the end.

Here is the function. It is short, but every line matters:

#include <algorithm>
 
vector<int> rebuildPath(const vector<int>& parent, int source, int target) {
    if (target != source && parent[target] == NONE) return {};
    vector<int> path;
    for (int v = target; v != NONE; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

Take E as the target in the town map. The loop visits these vertices in order: E, then F (the parent of E), then C (the parent of F), then A (the parent of C). The parent of A is NONE, so the loop stops. The list is E F C A. The reverse call turns it into A C F E.

The first if line handles one special case, covered in the next section. For the start vertex itself the loop runs once and returns {A}, which is the correct one-vertex path.

A helper prints a path with the vertex names:

#include <iostream>
#include <string>
 
void printPath(const vector<int>& path, const vector<char>& names) {
    if (path.empty()) {
        cout << "no path";
        return;
    }
    for (size_t i = 0; i < path.size(); ++i) {
        if (i > 0) cout << " -> ";
        cout << names[path[i]];
    }
}

Running it for every place from A gives these lines:

to A cost 0: A
to B cost 7: A -> B
to C cost 9: A -> C
to D cost 20: A -> C -> D
to E cost 20: A -> C -> F -> E
to F cost 11: A -> C -> F

The routes to D and E both cost 20, but they lead to different places, so neither one is a choice. A real tie is two routes to the same place with the same cost. The parent array keeps the one found first, and another order of roads could keep the other.

Unreachable targets

Some vertices cannot be reached from the start. Picture a road that leads to a closed bridge with no other way in. The parent of such a vertex stays NONE, the same value used for the start. The loop in rebuildPath would then return just the target, which looks like a valid one-stop path. It is wrong.

That is why the function checks first: if the target is not the start and its parent is NONE, the target was never reached, so return an empty list. The caller can then say "no path" instead of printing a wrong route.

Here is a three-place example. S has a road to X, and X has a road to Y. Place Z has no roads at all:

to S: S | edges add up to 0, dist is 0
to X: S -> X | edges add up to 4, dist is 4
to Y: S -> X -> Y | edges add up to 5, dist is 5
to Z: unreachable, dist is INF

For Z, the distance is still the large sentinel INF, and the path is empty. The program reports "unreachable" based on the empty path.

Checking the path against its cost

A useful habit is to check your rebuilt path against the distance table. Add up the weights of the roads on the path. The total must equal the distance. If it does not, the parent array and the distances disagree, and something is wrong in the update code.

The check looks at each pair of neighbouring vertices in the path and finds the road between them:

long long total = 0;
for (size_t i = 1; i < path.size(); ++i) {
    for (const Edge& e : g[path[i - 1]]) {
        if (e.to == path[i]) total += e.weight;
    }
}

The run for Y in the unreachable example printed edges add up to 5, dist is 5, which agrees. The check is cheap, so use it while learning. In production code you usually keep it only in tests.

A harder example: a path through a maze

Shortest path reconstruction works the same way for any graph. A grid is a graph too: each open cell is a vertex, and each cell is joined to the cells above, below, left and right of it. Each move costs 1 step, so BFS finds the shortest route. BFS sets the parent when it first reaches a cell. The first time a cell is found is the shortest route to it, because BFS checks cells in order of distance.

Here is the maze, with S as the start, E as the exit, and # as a wall:

S.#.....
..#.##.#
...#..#.
##.##.#.
.......E

Each cell has a number: row times the number of columns, plus the column. That turns a two-dimensional position into one index for the parent array. The BFS loop looks like this:

int rows = static_cast<int>(maze.size());
int cols = static_cast<int>(maze[0].size());
auto id = [&](int r, int c) { return r * cols + c; };
 
int n = rows * cols;
vector<int> dr = {-1, 1, 0, 0};
vector<int> dc = {0, 0, -1, 1};
vector<int> dist(n, -1), parent(n, NONE);
queue<int> q;
dist[source] = 0;
q.push(source);
while (!q.empty()) {
    int v = q.front();
    q.pop();
    int r = v / cols, c = v % cols;
    for (int k = 0; k < 4; ++k) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (maze[nr][nc] == '#') continue;
        int u = id(nr, nc);
        if (dist[u] != -1) continue;
        dist[u] = dist[v] + 1;
        parent[u] = v;
        q.push(u);
    }
}

The dist[u] != -1 check plays the same role as the distance comparison in Dijkstra. Once a cell has a distance, BFS never changes it, so the parent is never changed either.

After the search, rebuildPath(parent, source, target) returns the list of cell numbers. To draw the route, mark each cell in the list except the first and last with *:

steps from S to E: 11
path has 12 cells
S.#.....
*.#.##.#
***#..#.
##*##.#.
..*****E

There are 11 steps and 12 cells, because the list includes both the start and the exit. Eleven steps is one fewer than the number of cells, since each step moves between two cells. The drawing skips the first and last cell so that S and E stay visible.

Common mistakes

The most common mistakes come from the order of the steps in rebuildPath, and from the special cases. Each one below is a real run of the code, or a real compiler message.

Forgetting to reverse the list

If you return the list without reverse, the route comes out backwards. The following two lines came from a program that did not reverse, for the parent array of a three-place example (S has no parent, X comes from S, and Y comes from X):

2 1 0 | no reverse

The output reads Y, X, S, which is the route from Y back to S. The fix is the single reverse call before the return. Always check the first and last vertex in the output: the first must be the start.

Forgetting the unreachable check

Without the check at the start of rebuildPath, an unreachable target returns a one-vertex list. In the same three-place example, the vertex Z has no parent, so a program without the check printed:

3 | no check

That is just the number of Z, not a route. Any caller that expects the path to start at the source would now fail, or print a route that does not exist.

Missing the queue header

priority_queue lives in <queue>. A file that uses it without including that header fails to compile. The real message from g++ 15.2 was:

nohdr15.cpp:7:5: error: ‘priority_queue’ was not declared in this scope
    7 |     priority_queue<int> pq;
      |     ^~~~~~~~~~~~~~

g++ also prints a second error on the same line, which disappears once the header is added. Add #include <queue> at the top of the file.

Indexing past the end of the parent array

A vertex number must be between 0 and n - 1. If the target number comes from user input and is too big, the array access fails. Using at instead of [] turns the mistake into a clear error. The real message from this run was:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 7) >= this->size() (which is 5)

Plain [] does not check the index, so with the same bad number it may print garbage or crash without this message. When a vertex number comes from outside, check it or use at while learning.

Walking up a parent that points to itself

If you set parent[source] = source instead of NONE, the loop in rebuildPath never reaches NONE. The start vertex keeps pointing at itself, so the loop pushes it again and again until memory runs out. The fix is to leave the start's parent as NONE, which the code does by filling the array with NONE at the start of the search.

Setting the parent on every look

The parent must change only when the distance changes. If the code sets parent[e.to] = v before the if that compares distances, a longer route can overwrite a shorter one. The parent array then no longer matches the distance table, and the path check described above fails. Put the parent assignment inside the if block, next to the distance assignment.

Practice

Each exercise is followed by its answer. Try each one on paper before you read the answer.

Exercise 1: BFS by hand

An undirected graph has five vertices, numbered 0 to 4. Its edges, added in this order, are 0-1, 0-2, 1-3, 2-3 and 3-4. Each vertex's neighbour list keeps the order in which the edges were added. Run BFS from vertex 0 and write down the parent of vertex 4 and the path from 0 to 4.

Show the answer

The parent of 4 is 3. The path is 0 -> 1 -> 3 -> 4. The queue order was 0, then 1 and 2 (both neighbours of 0), then 3 (found from 1 first, since 1 was popped before 2), then 4 (found from 3). Vertex 3 has parent 1, not 2, because 1 was popped first.

Exercise 2: Dijkstra by hand

A graph has four places S, A, B and C, with these two-way roads and weights: S-A 1, S-B 4, A-B 2, A-C 6, and B-C 3. Find the shortest cost from S to C, and the route.

Show the answer

The cost is 6, and the route is S -> A -> B -> C. The route S -> A -> B -> C costs 1 + 2 + 3 = 6. The route S -> A -> C costs 7, and S -> B -> C costs 7 as well, so both are worse.

Exercise 3: Why the start has no parent

The loop in rebuildPath stops when it reaches a vertex whose parent is NONE. Explain what would go wrong if the start vertex's parent were set to the start vertex itself, for example parent[0] = 0.

Show the answer

The loop would never reach NONE. The start would point to itself, so the loop would keep adding vertex 0 to the list forever. The list would grow until the program runs out of memory. The start must keep the NONE marker so the loop has a stopping point.

Exercise 4: Read a parent array

A search from vertex 0 gives this parent array: [NONE, 0, 0, 2, 3]. Write down the path from 0 to 4 in the normal order.

Show the answer

The path is 0 -> 2 -> 3 -> 4. Starting at 4, the parents are 3, then 2, then 0, then NONE. The list is 4 3 2 0, and reversing it gives 0 2 3 4.

Summary

• A distance table says how far each vertex is. A parent array says how you got there, and both come from the same search.
• Set parent[u] = v in Dijkstra only inside the if that improves the distance, so the parent always matches the best route.
• Rebuild a path by walking from the target through the parents until you reach the start, then reverse the list.
• Use a marker such as NONE for the start and for unreachable vertices, and check for unreachable targets before you walk.
• Check the rebuilt path by adding up its edge weights and comparing with the distance table.