Let us see how we can compute shortest paths in directed acyclic graphs in linear time....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Let us see how we can compute shortest paths in directed acyclic graphs in linear time. A directed acyclic graph (DAG) is a directed graph with no directed cycles. See Figure 1 (a) for an example of a DAG. A source vertex in a directed graph is a vertex with no incoming edges, and a sink vertex in a directed graph is a vertex with no outgoing edges. For example, in Figure 1 (a), vertex A is a source, and vertex F is a sink. B 6 O 5 A N " 12 E 7 3 F 4 B 6 D сл -5 5 E 3 F 4 C B 6 D 10 -2 5 E F (a) (b) (c) Figure 1: (a) G, a directed acyclic graph (DAG); (b) G, after deleting vertex A; (c) G, after deleting A and C Puzzle 1 (a). Give an example of a directed graph with no source vertex and no sink vertex. If we delete A and all its adjoining edges from the graph Figure 1 (a), then we are left with the graph Figure 1 (b), in which C is a source vertex. And if we delete C and all its adjoining edges from Figure 1 (b), then we are left with the graph Figure 1 (c), in which B is a source vertex. Puzzle 1 (b). Prove that the above is true for all DAGS. In other words, prove that every DAG on n vertices contains at least one source vertex and at least one sink vertex. If you delete a source vertex and all its adjoining edges from the DAG, then the remaining DAG on (n-1) vertices also contains a source vertex. And if you delete that vertex and all its adjoining edges, then the remaining DAG on (n-2) vertices also contains a source vertex. You can keep deleting vertices in this manner, till you are left with only one vertex. Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s € V and te V, and a weight function w on the edges of G. For every edge e € E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+E). You Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s € V and t EV, and a weight function w on the edges of G. For every edge e € E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+ |E|). You may use the graph in Figure 1 (a) as a running example in your proof. 1 Puzzle 1 (d). Does your algorithm work for DAGS with negative edge weights also? If yes, then provide a proof. If no, then provide an example of a graph for which it fails. Let us see how we can compute shortest paths in directed acyclic graphs in linear time. A directed acyclic graph (DAG) is a directed graph with no directed cycles. See Figure 1 (a) for an example of a DAG. A source vertex in a directed graph is a vertex with no incoming edges, and a sink vertex in a directed graph is a vertex with no outgoing edges. For example, in Figure 1 (a), vertex A is a source, and vertex F is a sink. B 6 O 5 A N " 12 E 7 3 F 4 B 6 D сл -5 5 E 3 F 4 C B 6 D 10 -2 5 E F (a) (b) (c) Figure 1: (a) G, a directed acyclic graph (DAG); (b) G, after deleting vertex A; (c) G, after deleting A and C Puzzle 1 (a). Give an example of a directed graph with no source vertex and no sink vertex. If we delete A and all its adjoining edges from the graph Figure 1 (a), then we are left with the graph Figure 1 (b), in which C is a source vertex. And if we delete C and all its adjoining edges from Figure 1 (b), then we are left with the graph Figure 1 (c), in which B is a source vertex. Puzzle 1 (b). Prove that the above is true for all DAGS. In other words, prove that every DAG on n vertices contains at least one source vertex and at least one sink vertex. If you delete a source vertex and all its adjoining edges from the DAG, then the remaining DAG on (n-1) vertices also contains a source vertex. And if you delete that vertex and all its adjoining edges, then the remaining DAG on (n-2) vertices also contains a source vertex. You can keep deleting vertices in this manner, till you are left with only one vertex. Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s € V and te V, and a weight function w on the edges of G. For every edge e € E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+E). You Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s € V and t EV, and a weight function w on the edges of G. For every edge e € E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+ |E|). You may use the graph in Figure 1 (a) as a running example in your proof. 1 Puzzle 1 (d). Does your algorithm work for DAGS with negative edge weights also? If yes, then provide a proof. If no, then provide an example of a graph for which it fails.
Expert Answer:
Answer rating: 100% (QA)
Puzzle 1 a Directed Graph with No Source or Sink Vertex Example of a directed acyclic graph DAG with no source vertex and no sink vertex Explanation In this graph there is no vertex with incoming edges only source vertex and no vertex with outgoing edges only sink vertex Puzzle 1 b Proving the Existence of Source and Sink Vertices in DAGs We will prove that in any DAG with n vertices there must always exist at least one source vertex and at least one sink vertex Additionally when you repeatedly delete source vertices and their edges you will always end up with a graph that contains a source vertex until you are left with a single vertex Proof 1Base Case n 1 For a DAG with only one vertex it trivially contains a source vertex and a sink vertex the same vertex 2Inductive Hypothesis Assume that for any DAG with k vertices where k 1 there exists at least one source vertex and at least one sink vertex Furthermore after deleting a source vertex and its edges repeatedly the resulting graph on k 1 vertices will contain a source vertex 3Inductive Step Now consider a DAG with k 1 vertices a Case 1 There exists a vertex with no incoming edges If there is a vertex A with no incoming edges then A is a source vertex because no other vertex contributes edges to it In this case we have found a source vertex b Case 2 There is no vertex with no incoming edges In this case all vertices must have at least one incoming edge ... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these chemical engineering questions
-
The Database Administration Plan must contain the following items: 1. Create a detailed database administration plan to meet the needs of your retail organization. a. Include a transaction...
-
Write a literature review for your study. See below for an example of a literature review. Your literature review should provide both analysis and synthesis of previous studies as related to the...
-
Carol Harris, Ph.D, CPA, is a single taxpayer and she lives at 674 Yankee Street, Durham, NC 27409. Her Social Security number is 793-52-4335. Carol is an Associate Professor of Accounting at a local...
-
Clark had brain surgery. Insurance will not pay for the surgery until the deductible of $1,000 is hit. Then Clark's coinsurance of 80% / 20% kicks in. Clark has an out-of-pocket maximum of $7,500....
-
A block of mass 0.250 kg is placed on top of a light vertical spring of force constant 5 000 N/m and pushed downward so that the spring is compressed by 0.100 m. After the block is released from...
-
Gustavsson AB, manufacturer of tractors and other heavy farm equipment, is organized along decentralised lines, with each manufacturing division operating as a separate profit centre. Each divisional...
-
True or False: Only electric motors on variable-frequency drives (VFDs) have electric discharge machining (EDM) damage.
-
Isolation Company has a debt equity ratio of .80. Return on assets is 7.9 percent, and total equity is $480,000. What is the equity multiplier? Return on equity? Net income? Just Dew It Corporation...
-
1. What is the entry mode to a foreign country that Starbucks developed in their international strategy? Why choose this entry mode? Please explain in detail. 2. Has Starbucks adopted a...
-
Looking for the excel function in Yellow on Q9 Question 9 Annual 3.000% Semi-Annual 3.022% Quarterly 3.034% Monthly 3.042% 4 points Question 10 14.2 14.2 4 points 9) After reviewing the compounding...
-
a. Determine the values of a and b such that f is continuous everywhere: x + 3 f(x) = ax + b 3x - 11 if if x-1 -1 0
-
describe a specific example of the use of decision trees in business context. For example, decision trees can be used to forecast home buyer's willingness to close a deal. Directions: Explain what...
-
calculate the following employees gross pay and net income . Kim Jones works for an hourly rate of $7.50. This week Kim worked 39 hours. What is Kims gross pay for this week? She is paid weekly CC1....
-
describe about these Prizms: Based on their characteristics, way of life, and behaviours, each of the Prizms represents a certain population group. Downtown Verve Eat, Play, Love Suburban Sports...
-
Describe and scope your map Explain the scope of the topic or knowledge domain you have chosen to map. Consider what's included and what's not included in your mind map scope (i.e. put a boundary...
-
Describe the inspection regime mandated by the infrastructure controller for plain line Describe the inspection regime mandated by the infrastructure controller for switch and crossing Describe the...
-
Define Base Station
-
In Exercises discuss the continuity of each function. f(x) -3 1 x - 4 y 3 2 -1 -2 -3+ 3 X
-
Consider a model of computation that supports addition, comparison, and multiplication and for which there is a lower bound of (n lg n) to sort n numbers. Prove that (n lg n) is a lower bound for...
-
What is the probability that a k-string over a set of size n forms a k-permutation? How does this question relate to the birthday paradox?
-
What is the smallest value of n such that an algorithm whose running time is 100n 2 runs faster than an algorithm whose running time is 2 n on the same machine?
-
Form a small group. Concentrate on BSE Sensex companies and compile the voluntary disclosures made by each of them. Draft a crisp research paper highlighting your findings and use thereof to various...
-
Billy Ray Nibert was convicted of capital murder in the Circuit Court, Hillsborough County and he appealed. The Supreme Court of Florida affirmed the conviction, vacated the death sentence and...
-
Hassan Abu-Jihaad was convicted of disclosing national defense information and of providing material support to terrorist by a jury in the District Court of Connecticut. Abu-Jihaad moved for a...
Study smarter with the SolutionInn App