首页 » Python代写 » 算法分析代写|EECS 325 Analysis of Algorithms Homework 3

算法分析代写|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)

blank

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.


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank