$4.($U&G$-$required$)[30$ points$]$

a$)[10$ points$]$ Run the topological sort algorithm on the graph below and indicate the final

ordering of vertices obtained. In the main DFS loop, choose white vertices in alphabetical

order $($thus$,$ the initial source will be vertex a$).$ Also, assume that vertices are given in

alphabetical order in the adjacency list.

b$)[10$ points$]$ Run DAG$-$SHORTEST$-$PATHS on the directed graph from part $($a$),$ using

vertex e as the source.

c$)[10$ points$]$ Show how Dijkstra$$s algorithm runs on the graph below, with vertex d as the

source