Source code online books for professionals by professionals

DAG shortest path. Finds the shortest path from one node to all others in a DAG. Works by finding a topological 
sorting of the nodes and then relaxing all out-edges (or, alternatively, all in-edges) at every node from left to right. Can 
(because of the lack of cycles) also be used to find longest paths. Running time Q(n+m). (See Listing 8-4.)
Depth-first search (DFS). Traversing a graph (possibly a tree) by going in depth and then backtracking. Implemented 
by using a LIFO queue to keep track of discovered nodes. By keeping track of discover- and finish-times, DFS can 
also be used as a subroutine in other algorithms (such as topological sorting or Kosaraju’s algorithm). Running time 
Q(n+m). (See Listings 5-4, 5-5, and 5-6.)