# 算法分析代写｜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.