Use Prim$$s algorithm to compute the minimum spanning tree of G$.$

You can use the following table to describe the execution of the algorithm. The algorithm maintains a set S of vertices. The d value of a vertex v $/$ in S is minu in S:$($u$,$v$)$ in E w$($u$,$ v$).$

The $\backslash$pi value of a vertex v is the vertex u in S such that d$($v$)=$ w$($u$,$ v$)$; if d$($v$)=\backslash$infty $,$

then $\backslash$pi $($v$)=.$

You can try to complete the value of the table following the Prim algorithm in

our lecture notes, the edges in the MST are $,$ and the total weight is

$.$

$1$

iteration vertex added to S a b c d e

d $\backslash$pi d $\backslash$pi d $\backslash$pi d $\backslash$pi d $\backslash$pi

$1$ s $12$ s $\backslash$infty $20$ s $\backslash$infty $6$ s

$2$

$3$

$4$

$5$

Table $1$: Prim$$s Algorithm for Minimum Spanning Tree

$($b$)(6$ points$)$ Use Dijkstra$$s algorithm to compute the shortest paths from s to all

other vertices in G$.$

You can use the following table to describe the execution of the algorithm on the

instance. The algorithm maintains a set S of vertices. The d value of a vertex v $/$ in S

is minu in S:$($u$,$v$)$ in E$($d$($u$)+$ w$($u$,$ v$)).$ The $\backslash$pi value of a vertex v is the vertex u in S such

that d$($v$)=$ d$($u$)+$ w$($u$,$ v$)$; if d$($v$)=\backslash$infty $,$ then $\backslash$pi $($v$)=.$

iteration vertex added to S a b c d e

d $\backslash$pi d $\backslash$pi d $\backslash$pi d $\backslash$pi d $\backslash$pi

$1$ s $12$ s $\backslash$infty $20$ s $\backslash$infty $6$ s

$2$

$3$

$4$

$5$

Table $2$: Dijkstra$$s algorithm for Shortest Paths

The parents of vertices are:

a b c d e

parent

You can try to complete the value of the above two tables following the Dijkstra$$s

algorithm in our lecture notes. The shortest paths to a is $,$ and the length

is ; The shortest paths to b is $,$ and the length is ;

The shortest paths to c is $,$ and the length is ; The shortest

paths to d is $,$ and the length is ; The shortest paths to e is

$,$ and the length is