Solution Found!

Computer science / Algorithms 1 / Chapter 3 / Problem 3.25

Algorithms | 1st Edition | ISBN: 9780073523408 | Authors: Sanjoy Dasgupta Algorithms, Christos H. Papadimitriou Algorithms, Umesh Vazirani Algorithms

Change Question

You are given a directed graph in which each node u V has an associated price pu which

Chapter 3, Problem 3.25

(choose chapter or problem)

Get Unlimited Answers

QUESTION:

You are given a directed graph in which each node u V has an associated price pu which is apositive integer. Define the array cost as follows: for each u V ,cost[u] = price of the cheapest node reachable from u (including u itself).For instance, in the graph below (with prices shown for each vertex), the cost values of thenodes A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively.Your goal is to design an algorithm that fills in the entire cost array (i.e., for all vertices).(a) Give a linear-time algorithm that works for directed acyclic graphs. (Hint: Handle thevertices in a particular order.)(b) Extend this to a linear-time algorithm that works for all directed graphs. (Hint: Recall thetwo-tiered structure of directed graphs.)

Questions & Answers

QUESTION:

You are given a directed graph in which each node u V has an associated price pu which is apositive integer. Define the array cost as follows: for each u V ,cost[u] = price of the cheapest node reachable from u (including u itself).For instance, in the graph below (with prices shown for each vertex), the cost values of thenodes A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively.Your goal is to design an algorithm that fills in the entire cost array (i.e., for all vertices).(a) Give a linear-time algorithm that works for directed acyclic graphs. (Hint: Handle thevertices in a particular order.)(b) Extend this to a linear-time algorithm that works for all directed graphs. (Hint: Recall thetwo-tiered structure of directed graphs.)

ANSWER:

Step 1 of 2

(a)

Given a directed graph with cost values of the nodes. The Directed Acyclic Graph (DAG) algorithm for filling the entire cost array is given below.

Algorithm:

The node $u$ has edges to the nodes . The nodes are reachable from the node $u$ . It can be computed as follows.

.

Here, $e$ is the edge values and ${P}_{u}$ is the price value, it is a positive integer.

1. Start

2. It can iteratively compute the cost values of the nodes $x$ before computing .

3. The DAG computes the cost values in reverse topological sort order.

4. for each , apply a reverse topological sort to the following.

5.

6. END for

The algorithm uses the sorting of the vertices in topological order. So, the running time of the topological sorting is linear

Study Tools You Might Need

Chapter: 2 Problem: 33E

Conceptual Physics 12
Problem 33E Consider the normal force on a book at rest on a tabletop. If the table is tilted so that the surface forms an inclined plane, will the magnitude of the normal force change? If so, how?

Chapter: Problem: 5.2

OpenIntro Statistics 3
The figure on the right shows three unimodal and symmetric curves: the standard normal (z) distribution, the \(t\)-distribution with 5 degrees of freedom, and the \(t\)-distribution with 1 degree of freedom. Determine which is which, and explain your reasoning.

Chapter: 9 Problem: 3

Probability and Statistics 4
Suppose that a failure in a certain electronic system can occur because of either a minor or a major defect. Suppose also that 80 percent of the failures are caused by minor defects, and 20 percent of the failures are caused by major defects. When a failure occurs, n independent soundings X1,...,Xn a

Chapter: 4 Problem: 34

Elementary Statistics: A Step by Step Approach 8th ed. 8
Computer Ownership At a local university 54.3% of incoming first-year students have computers. If 3 students are selected at random, find the following probabilities. a. None have computers. 0.0954 b. At least one has a computer. 0.9046 c. All have computers. 0.1601

Chapter: 17 Problem: 17.28

Organic Chemistry, 9
Hydride reduction (with LiAlH4 or NaBH4) of each of the following ketones has been reported in the chemical literature and gives a mixture of two diastereomeric alcohols in each case. Give the structures of both alcohol products for each ketone. (a) (S)-3-Phenyl-2-butanone (b) 4-tert-Butylcyclohexano

Chapter: 3 Problem: P 3.5-3

Introduction to Electric Circuits 9
Determine the power received by each resistor in the circuit shown in Figure P 3.5-3.

Chapter: 1 Problem: 4

Biochemistry 9
In 1828, Whler was the first person to synthesize an organic compound (urea, from ammonium cyanate). How did this contribute, ultimately, to biochemistry?

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

×

Register

Sign up for access to all content on our site!

Or login if you already have an account