$(27$ voints$)1.$ Consider the following undirected weighted graph.

$(12$ points$)1\mathrm{.}1$ Use greedy methods to solve the minimum spanning tree of the given undirected

weighted graph.

Hint: reference to Section $21\mathrm{.}2$ in the textbook

$(6$ points$)1\mathrm{.}1\mathrm{.}1$ Illustrate a run of Kruskal's algorithm on this graph by stating at each step which

edge is added to the tree.

$(6$ points$)1\mathrm{.}1\mathrm{.}2$ Illustrate a run of Prim's algorithm on this graph starting from vertex A by

stating at each step which edge is added to the tree.

$(15$ points$)1\mathrm{.}2$ To solve all$-$pairs shortest paths, illustrate a run of the Floyd$-$Warshall algorithm

on this graph by calculating the distance matrix $D^{(k)}(k0)$ and the predecessor matrix ${}^{(k)}$

$(k0)$ at each step and show the shortest path from B to E according to the last predecessor

matrix.