Consider the following digraph

$($a$)$ Simulate Dijkstra's algorithm on the graph to find the shortest paths from node $0$ to all

other nodes. Specify for each call of relax

the node whose outgoing edges are relaxed,

the state of arrays distance and edge$\_$to after relaxing, and

the state of the priority queue after relaxing.

Additionally, draw the resulting shortest$-$path tree.

$($b$)$ Looking closer at the graph you realize that it is acyclic, meaning we can instead use the

specialized algorithm. First, specify a topological sort of the tree.

$($c$)$ Using your topological sort from $($b$),$ simulate the algorithm for acyclic graphs from the

lecture $($for node $0).$ Specify the current state of distance and edge$\_$to after each step.

$($d$)$ Why does Dijkstra's algorithm need a priority queue but the specialized algorithm for acyclic

graphs does not?