算法分析代写｜EECS 325 Analysis of Algorithms Homework 3

本次美国代写是一个Python算法分析的assignment

Question 1 (Minimum Spanning Trees and Shortest Paths, 18 points.) In this problem, you
will run each of Kruskal’s Algorithm, Dijkstra’s Algorithm, and Prim’s Algorithm for computing
minimum spanning trees (it computes the same thing as Kruskal’s Algorithm but looks nearly
identical to Dijkstra’s Algorithm) on the graph G in Figure 1, taking s = v1 as the source vertex
for the latter two algorithms. Pseudocode for a version of Dijkstra’s Algorithm slightly different
from the one we saw in class and for Prim’s Algorithm appears below.

Note that the pseudocode for Dijkstra’s Algorithm and Prim’s Algorithm is nearly identical.
The only substantive difference between the two algorithms (which is very important) is that in
Dijkstra’s Algorithm the priority of a vertex v in Q is the distance of v from s using only edges with
at least one endpoint in S whereas in Prim’s Algorithm it’s the lowest weight of an edge connecting
v to some vertex in S.

This version of Dijkstra’s Algorithm is very similar to the one we saw in class. The only difference
is that now instead of just computing distances δ(v; s) between each vertex v and s, it’s additionally
storing the predecessor vertex v:pred of each vertex v. Recursively following the predecessor pointers
v:pred of a vertex v back to s allows for easily computing the shortest path between s and v (not just
its length). The set of all n − 1 edges ffu:pred; ug : u 2 V n fsgg to predecessor vertices output by
Dijkstra’s Algorithm (respectively, Prim’s Algorithm) forms a minimum spanning tree (respectively,
shortest-paths tree with source vertex s)

For each algorithm, show the edge selected at each iteration of the main while loop|the one
added to the MST (for Kruskal and Prim) or to the shortest-paths tree (for Dijkstra). For Dijkstra
and Prim, this is edge is fu:pred; ug, i.e., the edge connecting u to some vertex in S. (When u = s
in the first iteration, this edge won’t exist; write \None”.)

(Hint: The MSTs output by Prim’s Algorithm and Kruskal’s Algorithm should be the same; this always
happens whenever all edge weights are distinct.)

a. (5 points.) Run Kruskal’s Algorithm on G.
b. (5 points.) Run Dijkstra’s Algorithm on G starting with source vertex s = v1.
c. (8 points.) Run Prim’s Algorithm on G starting with source vertex s = v1.