$($a$)(8$ points$)$ First simulate Dijkstra's algorithm by filling out the following table. Each

column represents a single round of Dijkstra's algorithm. In the top row write the

"active" vertex of that round, i$.$e$.$ the one popped from the queue which is the one

being set as the predecessor. Then for the other column entries, write the current

distance values, where you only need to fill in the entry if it changed since the previous

round. The first round, where $s$ is popped off the queue, has already been filled in$.$ No

explanation required.

$($b$)(6$ points$)$ Bellman$-$Ford does not specify which order it loops over the edges, but if the

right order is chosen Bellman$-$Ford only needs to do a single loop iteration. Give an

ordering of the edges for the graph above such that after a single loop iteration in the

Bellman$-$Ford algorithm the pred $(v)$ and dist$(v)$ values correctly describe a shortest

path tree. Briefly state the property your ordering has that ensures it gives the correct

values $($a single sentence explanation can suffice$).$

$($c$)(4$ Points$)$ Draw the MST of the following graph with the edges labeled by weight.

Alternatively, list the set of weights of the edges in the MST$.$ No explanation required.

$($d$)(5$ Points$)$ Give the weight of the fifth edge added when running Prim's algorithm for

the graph above, when starting from vertex $a.$ Give the weight of the fifth edge added

when running Kruskal's algorithm for the graph above. No explanation required.Problem $1.$ Running the algorithms $(23$ points$)$

In this problem you will simulate Dijkstra and Bellman$-$Ford on a graph.

For clarity, these algorithms are as follows:

The input graph is the followins.

$($a$)(8$ points$)$ First simulate Dijkstra's algorithm by filling out the following table. Each

column represents a single round of Dijkstra's algorithm. In the top row write the

"active" vertex of that round, i$.$e$.$ the one popped from the queue which is the one

being set as the predecessor. Then for the other column entries, write the current

distance values, where you only need to fill in the entry if it changed since the previous

round. The first round, where $s$ is popped off the queue, has already been filled in$.$ No

explanation required.

$($b$)(6$ points$)$ Bellman$-$Ford does not specify which order it loops over the edges, but if the

right order is chosen Bellman$-$Ford only needs to do a single loop iteration. Give an

ordering of the edges for the graph above such that after a single loop iteration in the

Bellman$-$Ford algorithm the pred$(v)$ and dist$($v$)$ values correctly describe a shortest

path tree. Briefly state the property your ordering has that ensures it gives the correct

values $($a single sentence explanation can suffice$).$

$($c$)(4$ Points$)$ Draw the MST of the following graph with the edges labeled by weight.

Alternatively, list the set of weights of the edges in the MST$.$ No explanation required.

$($d$)(5$ Points$)$ Give the weight of the fifth edge added when running Prim's algorithm for

the graph above, when starting from vertex $a.$ Give the weight of the fifth edge added

when running Kruskal's algorithm for the graph above. No explanation required.