1. Modify the algorithm for single-source shortest paths to actually store and return the shortest paths rather than just compute the distances.
2. The root of a DAG is a vertex R such that every vertex of the DAG can be reached by a directed path from R. Write an algorithm that takes a directed graph as input and determines the root (if there is one) for the graph. The running time of your algorithm should be Θ(|V| + |E|).