Problem $2(10$ points$)$

The graph shown on the right has negative weights so Dijkstra's algorithm cannot be used. Yet, it is possible to find the shortest paths from $s$ if the graph is a DAG. Apply the method described in the class and find the shortest paths from $s.$ In particular,

a$)(5$ pts$)$ Run DFS and show the discovery and finish times of the nodes. Then give the topological ordering of the nodes of the graph.

b$)(5$ pts$)$ Compute the distances from $s$ to all other nodes using the DP algorithm that can be found in the lecture notes.