Consider the following graph G with non$-$negative edge

weights.

$12$ a s

b c e

d

$123$

$10206$

$7$

$118$

$($a$)(6$ points$)$ 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 exec