Ed sample Final-s16.pdf x C Chegg study l Guided solu K- O uwm.edu/ Final-S16.pd

Question

Ed sample Final-s16.pdf x C Chegg study l Guided solu K- O uwm.edu/ Final-S16.pdf classes/cs535/HW/Sample 5. (3 pts.) Let G (V, E) be a directed acyclic graph (i.e., a DAG) in which each node v E V has an associated price pa, that is a positive integer. Let cost v price of the cheapest node that v can reach, including v itself Our goal is to output cost v for each v e V in an efficient manner. (i) (Warm-up!) Given the graph below where the numbers indicate the prices of each node. Please compute the cost of each node i.e., what is cost A cost Bl? etc. 5 AM 5/8/2017

Explanation / Answer

(i) Since E, F cannot reach any vertices cost(E) = price(E) = 4 and cost(F) = price(F) = 5.

For C, it can reach E, F so its cost(C)= min { price(C), price(E), price(F) } =min {6, 4 , 5} = 4

For A, it can reach C, E , F so its cost(A) = min{ price(A), price(C), price(E), price(F) } = min {2,6,4,5} = 2

For D, it can reach E, F so its cost(D)= min { price(D), price(E), price(F) } =min {1, 4 , 5} = 1

For B, it can reach D, E, F so its cost(B)= min { price(B), price(D), price(E), price(F) } =min {3, 1, 4 , 5} = 3

(ii)

Algorithm

-----------------

1) Since the graph is DAG, sort the vertices in reverse topological order, (this can be achieved by DFS and computing their finishing times and arranging the vertices in the increasing order of finishing times)

.2) Now in the above sorted list, starting from 1 to n, compute the cost of vertex u as below

cost[u] = min { price(u), {cost(v) for all v, such that (u,v) in E} }

Correctness:

---------------------

If we print the sorted list of vertices above, all the edges will go from right to left as it is reverse topological order.

So the first vertex doesnt have any outgoing edges so its cost will be set to its price, which is correct.

From the second vertex(v) onwards whatever vertices reachable from v, have to reached through the vertices that are at a one edge distance from v. These vertices will be on left side of v and their costs hold the minimum of all vertex prices that are reachable through it from v. so when we take minimum of these we are actually calculating the minimum of all vertices reachable from v. So this gives the correct answer.

Time complexity:

----------------------------

The first step in the algorithm is a DFS which takes O(n+m). And constructing the sorted order takes O(n) time.

In the seconds step we run a loop for all vertices and inside loop we only examine the edges going out that vertex, so each edge is processed only once so it takes O(n+m), So total time is O(n+m)

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.