Directed Acyclic Graphs: Depth-First Search

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 $G$ be a directed graph with weighted edges, and let $s$ be the fixed start vertex. For any vertex $v$, let $dist(v)$ denote the length of the shortest path in $G$ from $s$ to $v$. This function satisfies the following simple recurrence:

$$dist(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 $G$ contained a cycle, a recursive evaluation of this function would fall into an infinite loop; however, because $G$ 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 $G$: subproblem $dist(v)$ depends on $dist(u$ ...