- A F 3 3 5 5 6 B 7 E 4 3 4 D C 2 1 (17.34 KiB) Viewed 22 times
spanning tree starting with vertex A as the root node. Give
the starting vertex and the order in which vertices/edges would be
added to the tree.
2. Apply Prim's algorithm to produce the minimum
spanning tree starting with vertex D as the root node. Give
the starting vertex and the order in which vertices/edges would be
added to the tree.
3. What differences do you notice between the shapes of
the trees generated by (1) and (2)? What do you see about the
edges of graph G that are part of the MSTs generated by (1) and
(2)?
4. Apply Dijkstra's algorithm (using the modification to
Prim's MST algorithm) to find the shortest distance from vertex A
to every other vertex. Note what the distances are and what
edges are included in the resulting tree (that show the shortest
paths to the vertices). Create the tree formed (rooted at
vertex A) showing the shortest paths to every other
vertex.
5. Apply Dijkstra's algorithm (using the modification to
Prim's MST algorithm) to find the shortest distance from vertex D
to every other vertex. Note what the distances are and what
edges are included in the resulting tree (that show the shortest
paths to the vertices). Create the tree formed (rooted at
vertex D) showing the shortest paths to every other
vertex.
6. Compare the trees generated in your answers to (4)
and (5). Are the trees different? If so, what accounts
for their difference?
A F 3 3 5 5 6 B 7 E 4 3 4 D C 2