DFS、BFS和Dijkstra算法中的路径追踪

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 candidate paths between the start and target nodes in a graph found by the algorithms, and not just their lengths.

2. Tracing the Path in Recursive Depth-First Search

Depth-First Search (DFS) comes in two implementations: recursive and iterative. Tracing the shortest path to the target node in the former is straightforward. However, DFS isn’t guaranteed to find the shortest path between the start and target nodes, and, in some cases, the algorithm may run indefinitely.

We only have to store the nodes as we unfold the recursion after reaching the target node:

algorithm DepthFirstSearch(s, target):
    // INPUT
    //    s = the start node
    //    target = the function that identifies a target node
    // OUTPUT
    //    The shortest path between s and a target node
    
    if target(s):
        return [s]

    for v in neighbors(s):
        path <- DepthFirstSearch(v, target)
        
        if path != empty set:
            path <- prepend v to path
            return path
    
    return empty set

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 in the if statements executed in the for-loops after returning from the recursive calls until we return to . 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 to . Expanding the children of a node in the proper order, DFS finds the shortest path between and :

example1path

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

In this example, DFS found the shortest path, but if the order in which it visited the children of a node was different, the returned path could be suboptimal.

3. Tracing the Path in Iterative Depth-First Search

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

algorithm IterativeDepthFirstSearch(s, target):
    // INPUT
    //    s = the start node
    //    target = the function that identifies a target node
    // OUTPUT
    //    The target node closest to the start node, or an empty set meaning that no target is reachable

    if target(s):
        return s

    frontier <- a FIFO queue containing only s
    explored <- an empty set

    while frontier is not empty:
        u <- pop the most recently added node
        add u to explored

        for v in neighbors(u):
            if u is not in explored or frontier:
                if target(v):
                    return v
                add v to frontier

    return an empty set

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 and identified its children $v_1, v_2, \ldots, v_m$ . For each child, we have to memorize that its parent is :

algorithm IterativeDepthFirstSearchWithPathTracing(s, target, neighbors):
    // INPUT
    //    s = the start node
    //    target = the function that identifies a target node
    // OUTPUT
    //    The shortest path between s and a target node, or empty set meaning that no target is reachable
    
    if target(s):
        return s

    frontier <- a FIFO queue containing only s
    explored <- an empty set
    memory <- initialize the memory
    Set the parent of s to NULL

    while frontier is not empty:
        u <- pop the most recently added node
        Add u to explored

        for v in neighbors(u):
            Insert the information parent(v) = u into memory

            if u is not in explored or frontier:
                if target(v):
                    path <- reconstruct the path between s and v using memory
                    return path

                Add v to frontier

    return empty set

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:

algorithm BackwardPathReconstruction(s, t, memory):
    // INPUT
    //    s = the start node
    //    t = the target node found by DFS
    //    memory = a data structure containing the information on the parent-child relationships
    // OUTPUT
    //    the shortest path from t to s

    u <- t

    while u != null:
        print u
        u <- find the parent of u in memory

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:

algorithm ForwardPathReconstruction(u, s, t, memory):
    // INPUT
    //    s = the start node
    //    t = the target node found by DFS
    //    memory = a data structure containing the information on the parent-child relationships
    // OUTPUT
    //    The shortest path from s to t

    path <- an empty LIFO structure
    u <- t

    while u != null:
        push u onto path
        u <- find the parent of u in memory

    while path is not empty:
        u <- pop the node most recently added to path
        print u

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 is the node whose id is . Its parent is ![memory[memory[i]]](/wp-content/ql-cache/quicklatex.com-28fe98a5a7917d3000bcdac3bb605d1a_l3.svg "Rendered by QuickLaTeX.com"), 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 and :

example2

The same comment on the optimality of the path holds in this case.

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:

algorithm IterativeDFSWithPathMemorization(s, target, neighbors):
    // INPUT
    //    s = the start node
    //    target = the function that identifies a target node
    // OUTPUT
    //    The shortest path between u and a target node
    
    if target(s):
        return [s]

    frontier <- a FIFO queue containing only (s, [s])
    explored <- an empty set

    while frontier is not empty:
        (u, path_to_u) <- pop from frontier the most recently added pair
        Add u to explored
        
        for v in neighbors(u):
            path_to_v <- append v to path_to_u
            Insert (v, path_to_v) into memory
            
            if u is not in explored or frontier:
                if target(v):
                    return path_to_v
                Add (v, path_to_v) to frontier
    
    return empty set

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

4. Tracing the Path in Breadth-First Search

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:

algorithm BreadthFirstSearch(s, target, neighbors):
    // INPUT
    //    s = the start node
    //    target = the function that identifies a target node
    // OUTPUT
    //    The shortest path between s and a target node, if one exists. 
    //    Otherwise, the algorithm returns an empty set.
    
    if target(s):
        return s

    frontier <- a FIFO queue containing only s
    explored <- an empty set
    s.parent <- null
    t <- null

    while frontier is not empty:
        u <- pop the oldest node
        Add u to explored

        for v in neighbors(u):
            v.parent <- u

            if u is not in explored or frontier:
                if target(v):
                    t <- v
                    break
                Add v to frontier
        
        if target(v):
            break

    if t is null:
        return empty set
    else:
        path <- reconstruct the path from s to t
        return path

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 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 to 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:

algorithm Dijkstra(s, G):
    // INPUT
    //    s = the start node
    //    G = a graph
    // OUTPUT
    //    dist = the lengths of the shortest paths from s to all the other nodes in the graph
    //    prev = an array such that if prev[j] = i, then the shortest path from s to j finishes with the branch j->i

    queue <- make an empty min-priority queue

    for vertex v in G:
        dist[v] <- infinity
        prev[v] <- null
        Add v to queue with the value infinity

    dist[s] <- 0

    while queue is not empty:
        u <- extract the vertex with the highest priority (minimal value) in queue

        for v in neighbors of u still in the queue:
            alt <- dist[u] + weight(u, v)

            if alt < dist[v]:
                dist[v] <- alt
                prev[v] <- u
                Decrease the priority of v in the queue according to the new value dist[v]

    return (dist, prev)

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

algorithm BackwardPathReconstruction(s, t, prev):
    // INPUT
    //    s = the start node
    //    t = the target node
    //    prev = the result of Dijkstra's Algorithm
    // OUTPUT
    //    The shortest path from t to s, if one exists. An empty array otherwise.

    u <- t
    path <- an empty array

    while u != null:
        path <- prepend u to path
        u <- prev[u]

    return path

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.

Persistence

REST

Security