DAGs

A directed acyclic graph is a graph that has no cycles, and flows in a single direction.

We can use Depth First Search to find out if there is a cycle.

Note

A directed graph has a cycle if DFS reveals a back edge.

We can check this through the following:

1. Run Depth First Search on G
2. For each edge, check that $I_u$ is contained in $I_v$. If there is such an edge, then G has a cycle. DAGs are interesting because they represent that task u should be performed before v and the edges represent causal relationships.

We can perform Topological Sort on DAGs.

Shortest Path

We can use a Topological Sort to get an efficient algorithm for finding the shortest path in DAGs.

procedure dag-shortest-paths(G,l,s)  
Input: a DAG G = (V, E); edge lengths l_e for each e in E; and a start vertex s in V  
Output: For all u reachable from s, dist(u) is set to the distance from s to u  
	for all u in V:
		dist(u) = inf
	dist(s) = 0
	topologically sort G  
	for u in V in topological order:
		for all edges (u, v) in E:
		update((u, v))

Since updates are performed in topological order, they are sure to find the shortest paths in the DAG. The runtime here is $O(V+E)$ which comes from the topological sort.