Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll show how to trace paths in three algorithms: Depth-First Search, Breadth-First Search, and Dijkstra’s Algorithm. More precisely, we’ll show several ways to get the shortest paths between the start and target nodes in a graph, and not just their lengths.

Depth-First Search (DFS) comes in two implementations: recursive and iterative. Tracing the shortest path to the target node in the former is straightforward. We only have to store the nodes as we unfold the recursion after reaching the target node:

Rendered by QuickLaTeX.com

Here, we treated path as an array and prepended the nodes to it to have them in the order from the start node to the target. An alternative would be to use a stack. However, if the order doesn’t matter, we can avoid using a separate data structure for the path. We can print the current node as soon as it passes the target test and keep printing v in the if statements executed in the for-loops after returning from the recursive calls until we return to s. That way, we avoid using additional memory.

2.1. Example

Let’s use the following graph as an example:

example1

We want the shortest path from S to T. Expanding the children of a node in the proper order, DFS finds the shortest path between S and T:

example1path

Then, it returns [T] to the call in which it expanded C and prepends C to [T] to get [C, T]. Doing the same with B and A, DFS returns [A, B, C, T] to the original call, prepends S to it, and gives us [S, A, B, C, T] as the shortest path.

However, recursive DFS may be slower than the iterative variant:

Rendered by QuickLaTeX.com

There are two ways we can trace the path in the iterative DFS. In one approach, after visiting a node, we memorize which node its parent is in the search tree. That way, after finding the target node, we can reconstruct the path by following the parent-child hierarchy. In the other method, we store the full path to each node. Thus, when the search ends, the one leading to the target node is available as well.

We can implement both techniques using different data structures, with or without recursion. All the ways work the same, and which one we’ll choose is largely a matter of our preference.

3.1. Memorizing the “Family Ties”

The key idea is to memorize the parents of the nodes we explore. Let’s say that we expanded a node u and identified its children v_1, v_2, \ldots, v_m. For each child, we have to memorize that its parent is u:

Rendered by QuickLaTeX.com

3.2. Reconstructing the Path

Then, to reconstruct the path, we only have to read the memory to get the target’s parent, its parent afterward, and so on until we reach the start node:

Rendered by QuickLaTeX.com

This way, we get the path from the target node to the start node. If we want it the other way around, then we should print the path in reverse:

Rendered by QuickLaTeX.com

3.3. How to Implement the Memory

We can represent the information that \boldsymbol{u} is the parent of \boldsymbol{v} using different data structures. For example, we can store a pointer to \boldsymbol{u} in \boldsymbol{v}. Then, reading the memory amounts to traversing a linked list.

We can also use hash maps. A common approach is to assign a unique positive integer to each node as its id, treat the ids as indices, and store the parent-child information in an array. Let’s say that memory is that array. Then, the parent of node i is the node whose id is memory[i]. Its parent is memory[memory[i]], and so on.

3.4. Example

This is DFS would grow memory if it expanded the nodes in the order which corresponds to the shortest bath between S and T:

example2

3.5. Memorizing the Path While Searching

We can also keep track of the paths to the currently active nodes while running DFS. After expanding the node \boldsymbol{u}, we remember the paths to the children of \boldsymbols{u} that are its children in the search tree, and once the algorithm identifies a target node, we know we already have the path to it. Therefore, we don’t have to reconstruct it from the memorized information:

Rendered by QuickLaTeX.com

This approach is similar to path tracing in the recursive DFS. However, we use more memory because we keep the full paths to all the nodes in the \bodsymbol{frontier}. In the recursive DFS, we only keep track of one path.

3.6. Example

This approach would work like this on the previous example:

example3-1

The same approaches that we used for DFS work as well for Breadth-First Search (BFS). The only algorithmic difference between DFS and BFS lies in the queue: the former uses a LIFO, whereas the latter uses a FIFO implementation. However, that causes BFS to use way more memory than DFS, so path storing may not be our best option. Instead, we should consider extending the nodes with the pointers to their parents or use a hash map. That method won’t induce much memory overhead:

Rendered by QuickLaTeX.com

We reconstruct the path just as in Algorithm 5. The only thing we should pay attention to is that the line “u \leftarrow find the parent of u in memory” in Algorithm 5 should be implemented as “u \leftarrow u.parent” to work with our BFS.

4.1. Example

This is how BFS would find the path from S to T in our example:

example bfs

5. Tracing the Path in Dijkstra’s Algorithm

Unlike DFS and BFS, Dijkstra’s Algorithm (DA) finds the lengths of the shortest paths from the start node to all the other nodes in the graph. Though limited to finite graphs, DA can handle positive-weighted edges in contrast to DFS and BFS.

We apply the same idea with the memory as before and adapt it to DA. The algorithm will update the memory as soon as it updates the currently known length of the shortest path between a node in the graph and the start node. The array prev plays the role of the memory in the pseudocode of DA with path tracing:

Rendered by QuickLaTeX.com

Using prev, we can reconstruct the path between s and any node t:

Rendered by QuickLaTeX.com

As we see, it’s the same strategy we used in DFS.

6. Conclusion

In this article, we showed several ways to trace the paths in Depth-First Search, Breadth-First Search, and Dijkstra’s Algorithm.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!