Directed Acyclic Graphs: Depth-First Search

Explore the different techniques used to implement the depth-first search algorithm efficiently.

Shortest paths in acyclic graphs

Shortest paths are also easy to compute in directed acyclic graphs, even when the edges are weighted, and in particular, even when some edges have negative weight. (We don’t have to worry about negative cycles because, by definition, dags don’t have any cycles!) Indeed, this is a completely standard dynamic programming algorithm.

Let GG be a directed graph with weighted edges, and let ss be the fixed start vertex. For any vertex vv, let dist(v)dist(v) denote the length of the shortest path in GG from ss to vv. This function satisfies the following simple recurrence:

dist(v){0if v=sminuv(dist(u)+w(uv))otherwisedist(v)\begin{cases} & 0 \hspace{4.1cm} if\space v=s \\ & \underset{u\rightarrow v}{min}(dist(u) + w(u\rightarrow v)) \hspace{0.4cm} otherwise \end{cases}

In fact, this identity holds for all directed graphs, but it is only a recurrence for directed acyclic graphs. If the input graph GG contained a cycle, a recursive evaluation of this function would fall into an infinite loop; however, because GG is a dag, each recursive call visits an earlier vertex in topological order.

The dependency graph for this recurrence is the reversal of the input graph GG: subproblem dist(v)dist(v) depends on dist(u)dist(u) if and only if uvu\rightarrow v is an edge in GG. Thus, we compute the distance of every edge in O(V+E)O(V + E) time by performing a depth-first search in the reversal of GG and considering vertices in postorder. Equivalently, we can consider the vertices in the original graph GG in topological order.

Bellman-Ford algorithm with predecessor pointers

The resulting dynamic-programming algorithm is another example of Ford’s generic relaxation algorithm! To make this connection clearer, we can move the initialization dist(v)dist(v) outside the main loop and add computation of predecessor pointers, as shown below.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy