10.13 Reconstructing Shortest Paths

Most shortest-path algorithms compute distances. They tell us that the minimum cost from a source to a destination is:

or:

In practice, this information is often insufficient.

A navigation system must display the route. A network router must know which links to traverse. A workflow engine must know which sequence of tasks leads to the optimal outcome.

The actual path is frequently more important than its cost.

Fortunately, path reconstruction requires only a small extension to the shortest-path algorithms already covered in this chapter.

Problem

Given a shortest-path algorithm that computes distances, reconstruct the actual shortest path from a source vertex to a target vertex.

Consider:

A --2--> B --3--> D
 \                ^
  \              /
   5            1
    \          /
      C ------

Suppose Dijkstra computes:

distance[D] = 5

We want to recover:

A -> B -> D

rather than merely knowing that the cost is five.

Solution

Maintain a predecessor array.

Whenever a shortest-path relaxation improves a distance:

if candidate < dist[next] {
	dist[next] = candidate
	parent[next] = current
}

The predecessor records the vertex immediately preceding the destination on the shortest path.

After the algorithm finishes, follow predecessor links backward.

package main

import "fmt"

func buildPath(
	parent []int,
	source int,
	target int,
) []int {

	if source == target {
		return []int{source}
	}

	if parent[target] == -1 {
		return nil
	}

	var path []int

	for v := target; v != -1; v = parent[v] {
		path = append(path, v)
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

func main() {
	parent := []int{
		-1,
		0,
		0,
		1,
	}

	fmt.Println(
		buildPath(parent, 0, 3),
	)
}

Output:

[0 1 3]

This corresponds to:

0 -> 1 -> 3

Understanding the Parent Array

Suppose Dijkstra discovers:

A -> B = 4

Initially:

distance[B] = 4
parent[B] = A

Later, a better path appears:

A -> C -> B = 2

The update becomes:

distance[B] = 2
parent[B] = C

The old predecessor is discarded.

The parent array always reflects the currently best known path.

When the algorithm terminates, the array describes a shortest-path tree rooted at the source.

Visualizing the Tree

Consider:

      A
     / \\n    B   C
   /   / \\n  D   E   F

Shortest-path computation might produce:

parent[A] = nil
parent[B] = A
parent[C] = A
parent[D] = B
parent[E] = C
parent[F] = C

This forms:

A
├─ B
│  └─ D
└─ C
   ├─ E
   └─ F

Every vertex points toward the source.

Reconstructing a path simply follows those pointers.

Why Backtracking Works

Suppose:

parent[D] = B
parent[B] = A
parent[A] = nil

Starting at:

we obtain:

D
B
A

This sequence is reversed.

After reversal:

A
B
D

which is the desired path.

The process succeeds because every predecessor points one step closer to the source.

Path Reconstruction in BFS

BFS naturally supports path reconstruction.

for _, next := range graph[current] {
	if visited[next] {
		continue
	}

	visited[next] = true
	parent[next] = current

	queue = append(queue, next)
}

The first discovery of a vertex is guaranteed to be optimal.

Therefore the recorded predecessor belongs to a shortest path.

The reconstruction procedure remains unchanged.

Path Reconstruction in Dijkstra

Dijkstra updates predecessors whenever a distance improves.

if candidate < dist[next] {
	dist[next] = candidate
	parent[next] = current
}

Because Dijkstra eventually computes optimal distances, the resulting predecessor tree contains shortest paths.

The reconstruction code is identical to BFS.

Only the relaxation logic differs.

Path Reconstruction in Bellman-Ford

Bellman-Ford uses the same predecessor update.

if candidate < dist[next] {
	dist[next] = candidate
	parent[next] = current
}

The algorithm repeatedly improves distances.

Each improvement updates the parent.

At termination, the predecessor chain corresponds to a shortest path.

The reconstruction procedure remains exactly the same.

This consistency is useful.

The shortest-path algorithm changes.

The reconstruction algorithm does not.

Reconstructing All Paths

Suppose we want every shortest path from the source.

After the shortest-path computation finishes:

for vertex := range graph {
	path := buildPath(
		parent,
		source,
		vertex,
	)

	fmt.Println(path)
}

The predecessor tree immediately provides routes to every reachable vertex.

No additional graph search is required.

Handling Unreachable Vertices

Consider:

A -> B

C

Starting from:

vertex:

cannot be reached.

The predecessor remains:

parent[C] = -1

When reconstruction begins:

if parent[target] == -1 {
	return nil
}

the algorithm correctly reports that no path exists.

Always handle this case explicitly.

Multiple Shortest Paths

Shortest paths are not necessarily unique.

Consider:

A -> B -> D
A -> C -> D

with costs:

1 + 1 = 2
1 + 1 = 2

Both routes are optimal.

The predecessor array records only one.

Which one appears depends on:

Edge ordering
Queue ordering
Heap ordering
Relaxation order

This behavior is usually acceptable.

If all shortest paths must be enumerated, additional information must be stored.

Storing Multiple Parents

Instead of:

parent[next] = current

maintain:

parents[next] = append(
	parents[next],
	current,
)

whenever an equally short path is discovered.

For example:

if candidate < dist[next] {
	dist[next] = candidate
	parents[next] = []int{current}
} else if candidate == dist[next] {
	parents[next] =
		append(parents[next], current)
}

The resulting structure becomes a shortest-path DAG rather than a tree.

All optimal routes can then be enumerated.

Reconstructing Paths in Floyd-Warshall

Floyd-Warshall computes all-pairs shortest paths.

A predecessor array is insufficient because there is no single source.

Instead maintain:

next[i][j]

representing the next vertex after i on the shortest path to j.

Initialization:

next[i][j] = j

When a better route through k is discovered:

next[i][j] = next[i][k]

The full path is reconstructed by repeatedly following:

next

until the destination is reached.

Discussion

Path reconstruction highlights an important principle.

Shortest-path algorithms compute two different products:

Distance information
Structural information

The distance tells us:

How good is the solution?

The predecessor structure tells us:

What is the solution?

Many systems ultimately care more about the second question.

The additional memory cost is small.

The practical value is enormous.

For this reason, predecessor tracking is almost always enabled in production shortest-path systems.

Complexity

Let:

L = path length

Path reconstruction follows one predecessor per path vertex.

Operation	Complexity
Store predecessor	O(1)
Reconstruct path	O(L)
Reverse path	O(L)
Extra memory	O(V)

The overhead is negligible compared to the shortest-path computation itself.

Common Mistakes

Do not forget to update predecessors whenever a shorter path is discovered.

Do not assume a predecessor tree contains all shortest paths.

Do not attempt reconstruction before the shortest-path computation finishes.

Do not forget unreachable-vertex checks.

Do not confuse predecessor trees with spanning trees. A shortest-path tree is determined by path costs rather than graph connectivity alone.

Practical Applications

Path reconstruction appears in:

GPS navigation
Network routing
Logistics planning
Robot navigation
Workflow optimization
Game AI
Dependency analysis
Transportation systems

In most applications, the route is ultimately the product being delivered to the user.

Takeaway

Shortest-path algorithms become substantially more useful when augmented with predecessor information. By recording the vertex responsible for each distance improvement, we obtain a shortest-path tree that allows routes to be reconstructed efficiently. The technique works uniformly across BFS, Dijkstra, Bellman-Ford, and many other shortest-path algorithms, making it one of the most valuable implementation patterns in graph programming.