Modified Search Problem: Find Distance

  • Describe a variant of the general Graph Search problem that finds the distance between a source and every reachable vertex. Distance is defined as the length of a path from the source to that vertex.
  • Modify BFS/DFS to find the distance between a source and every reachable vertex, where distance is the length of a path from the source to that vertex.

Let us further modify the goal of the General Graph Search problem:

Goal: Find the distance of each (reachable) vertex in $G$ to $s$, where "distance" is defined as the length of a path from $s$ to the other vertex.

Let's make the observation that on a path from $s$ to $v$ and then to $u$ following the edge $(v, u)$, we have $d(u)=d(v)+1$ where $d(x)$ is the distance of vertex $x$ to the source $s$.

The demo here uses BFS, but we could do the same with DFS!

Demo

The following pseudocode describes the BFS algorithm. 

// Pre: "s" is the source vertex
explored = {}
explored[s] = true 
queue.enqueue(s)
while (!queue.empty())
    v = queue.dequeue()
    for (w in adjacency[v])
        if (!explored[w])
            explored[w] = true    
            queue.enqueue(w)

Exercise Modify it to include and update the distance collection according to the demo.

Solution 
distance = {}
explored = {}
distance[s] = 0 
queue.enqueue(s)
while (!queue.empty())
    v = queue.dequeue()
    for (w in adjacency[v])
        if (!explored[w])
            explored[w] = true    
            queue.enqueue(w)
            distance[w] = distance[v] + 1