ECS 122A – Algorithm & Analysis Homework 07 Solution
Question 1 (15 points)
Suppose you are given a directed graph G in which every edge has negative weight, and a source vertex s. Describe an algorithm that computes the shortest-path distances from s to every other vertex in G and analyze the runtime. Specifically, for every vertex t:
• If t is not reachable from s, your algorithm should report d[t] = ∞.
Copyright By PowCoder代写 加微信 powcoder
• If G has a cycle that is reachable from s, and t is reachable from that cycle, then the shortest-path distance from s to t is not well-defined, because there are paths from s to t of arbitrarily large negative length. In this case, your algorithm should report d[t] = −∞.
• Ifneitherofthetwopreviousconditionsapplies,youralgorithmshouldreportthecorrectshortest- path distance from s to t.
Modify the Bellman-Ford algorithm:
After the loop for going through the edges for |V| − 1 times, instead of checking for tense edges by going the through the edges one more time, go through the edges for |V| more times and update the distance to be negative infinity whenever there is a tense edge, i.e.,
for i = 1 to |V|:
for each edge u->v:
if v.d > u.d + w(u,v): v.d = -infinity
Follow up question: Why does it have to be |V| times and not |V| − 1? Question 2 (15 points)
Given the following graph, find the MST of the graph using Prim’s algorithm. Suppose the root is A. State at each step how the key and predecessor arrays are updated.
ABCDEFG init 0,N ∞,N ∞,N ∞,N ∞,N ∞,N ∞,N
A B F C E G D
6, A 5, B 2, F
10, A 7, F
Question 3 (20 points)
Let G = (V, E, w) be an arbitrary undirected, connected and weighted graph. (Assume the edge weights are distinct.)
Prove or disprove: The minimum spanning tree of G includes the minimum-weight edge in every cycle of G.
Answer: Disprove:
In the following graph, the MST is {(a,b),(a,c),(b,d)} but the minimum weight edge of the cycle {b, c, d, b} is (b, c).
Question 4 (30 points)
Describe an algorithm that computes the maximum-weight spanning tree of an undirected, connected and weighted graph.
Answer: Negate the edge weights. Run any of the minimum-spanning tree algorithm. The result tree would be the maximum-spanning tree. To get the weight of the tree, simply add up the edge weights and negate it.
Question 5 (20 points)
Given an undirected, connected and weighted graph G = (V, E, w) in which the weight for every edge is 1, describe an algorithm with runtime O(E) that finds the minimum-spanning tree of the graph.
Run DFS on the graph. The resulting DFS tree would be a minimum spanning tree. The runtime of DFS
is O(|V| + |E|). Since the graph is connected, |V| is O(|E|). So the runtime is O(|E|).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com