Problem $1.$ SSLP $(10$ points$)$

For this problem, we'll modify Dijktra's to compute the longest paths from a source vertex $s$ to all

other vertices in a weighted, directed, acyclic graph. $($Note that this is a hard problem for a general

graph. But doable for a DAG!$)$

$($a$)$ For the graph above, give a valid topological sort of the vertices.

Solution:

$($b$)$ Give pseudocode for an algorithm to compute the longest paths on a DAG like the one above.

Your algorithm should take a graph $G$ represented in an adjacency list, a source vertex $s,$ and

a weight function $w,$ and you can assume that the vertices are topologically sorted. $($Hint: You

can call$/$modify any helper functions we've seen in class.$)$

Solution:

$($c$)$ Give the final $v.d$ and $v.$ values your algorithm would generate for the graph above.

Solution: