Minimum Spanning Trees and Shortest Paths
Assignment 10
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Minimum spanning trees (8 points)
Suppose that an MST of the following edge-weighted graph contains the edges with weights
x, y, and z.
-
Which one or more of the following can be the value of
x?5 15 25 35 45 55 65 75 85 95 105 115 125 135 145 -
Which one or more of the following can be the value of
y?5 15 25 35 45 55 65 75 85 95 105 115 125 135 145 -
Which one or more of the following can be the value of
z?5 15 25 35 45 55 65 75 85 95 105 115 125 135 145
Exercise 2: Shortest paths (8 points)
Suppose that you are running Dijkstra's algorithm on the edge-weighted digraph below,
starting from vertex 0.
The table below gives the edgeTo[] and distTo[] values immediately after
vertex 4 has been deleted from the priority queue and relaxed.
- Give the order in which the first four vertices were deleted from the priority queue and relaxed.
- What are all possible values of the weight of the edge
x? - What are all possible values of the weight of the edge
y? - Which is the next vertex to be deleted from the priority queue and relaxed?
-
In your submission, provide only those entries in the
edgeTo[]anddistTo[]arrays that change when the next vertex is deleted from the priority queue and relaxed.