ECS 122A – Algorithm & Analysis Homework 06 Solution
Question 1 (44 points)
Given the following directed graph,
1. (5 points) Write down the adjacency list representation of the graph, assuming all vertices are ordered alphabetically.
Copyright By PowCoder代写 加微信 powcoder
q : s,t,w r : u, y s:v
t : x, y u:y v:w w:s x:z y:q z:x
2. (5 points) Write down the adjacency matrix representation of the graph, assuming all vertices are ordered alphabetically. Answer:
qrstuvwxyz q0011001000 r0000100010 s0000010000
t0000000110 u0000000010 v0000001000 w0010000000 x0000000001 y1000000000 z0000000100
3. (10 points) Perform breadth-first search on the graph with the source being r. Draw the table for the distance and predecessor arrays.
q r stuvwxyz d2 0 33143415 π y NULL q q r s q t r x
4. (20 points) Perform depth-first search on the graph.
• Show the discovery and finishing times for each vertex. • Show the classification of each edge.
Question 2 (26 points)
Given the following directed graph, find the shortest paths from every node to node 1 using the Dijkstra’s algorithm.
1. Modifytheinputgraphbyreversingalltheedgedirections.Sotheproblemisequivalenttosolving
the SSSSP problem.
2. Initialization:
3. Iteration 1: extract 1
4. Iteration 2: extract 2
5. Iteration 3: extract 3
6. Iteration 4: extract 4
7. Iteration 5: extract 6
8. Iteration 6: extract 5. The distances and precedessors remain the same. 9. Iteration 7: extract 7. The distances and precedessors remain the same.
Note: No need to draw a copy of the graph for each step. A table of the updates like what we did for Bellman-ford is also acceptable.
Question 3 (25 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:
Question 4 (30 points)
Given a weighted graph G = (V, E, w) and a source vertex s ∈ V, prove the the following properties regardless of the SSSP algorithm.
• (15 points) If π[s] ever changes after the initialization, then G contains a negative cycle through s. Answer:
Suppose π[s] is changed after the initialization. It means at some point for some vertex u, we have s.d > u.d + w(u, s).
Suppose this is the first time π[s] is changed, i.e., s.d = 0 and u.d + w(u, s) < 0. There is a cycle through s. Reasons:
– u.d̸=∞meansthereisapathfromstou. – w(u, s) means there is an edge from u to s.
The cycle is negative because u.d + w(u, s) < 0.
• (15 points) Show that π[s] may never change after the initialization, even when G contains a nega-
tive cycle through s.
Answer: If we perform Dijkstra’s algorithm on the above graph, π[s] remains None.
The result is shown belove.
Other algorithms have other graphs as examples. I only included one for Dijkstra’s.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com