Find the critical path for the graph

Assignment Help Basic Computer Science

Reference no: EM131412944

A critical path in a weighted, directed, acyclic graph is the path with the greatest weight. Let's assume that all edge weights are positive. Give each vertex a value equal to the weight of a path to that vertex. Initially, each vertex's value is zero. We can find the critical path by considering the vertices one at a time in topological order. For each vertex, consider all the edges that leave the vertex. For each of these edges, add the weight of the edge and the value of the edge's source vertex. Compare the sum with the value of the edge's destination vertex. Make the larger of these values the value of the destination vertex. After all vertices have been visited, the largest value stored in a vertex will be the weight of the critical path. Find the critical path for the graph in Figure 28-23.

Reference no: EM131412944

Questions Cloud

Are you doing a one-tailed test or a two-tailed test : A drug company is measuring levels of oxygenation in patients after receiving a test medication. As the researcher, you are interested in whether Group I, which received the medication, has the same oxygenation levels as Group II, which did not.

Grow at some constant rate g throughout time : A stock is trading at $ 44 .00 per share. The stock is expected to have a year-end dividend of $ 3.1 0 per share (D1), which is expected to grow at some constant rate g throughout time.

Which structures was specific to the animal cell : Which of the following structures was specific to the animal cell? Which of the following structures was specific to the plant cell? The large solid spot within the nucleus is the __________.

Determine the truth value - lincoln wrote the gettysburg : Write the following compound statements in symbolic form, then use your knowledge of the historical events referred to by the simple statements to determine the truth value of the compound statements.- Lincoln wrote the Gettysburg Address if and o..

Find the critical path for the graph : Make the larger of these values the value of the destination vertex. After all vertices have been visited, the largest value stored in a vertex will be the weight of the critical path. Find the critical path for the graph in Figure 28-23.

What is the net asset value of the fund : A mutual fund has 100 shares of ABC Company that currently trade at $12 per share and 200 shares of XYZ Company that trade at $8 per share. If the fund has 50 shares, and the liability worth $500 what is the net asset value of the fund?

Describe what cloud computing is : IT 100 : In a professional career, one may be called upon to conduct research and deliver findings in professional settings. No matter how extensive the research or accurate the conclusions, a weak presentation can undermine an argument. A present..

What lump sum deposited today : What lump sum deposited today at 8% compounded quarterly for 10 years will yield the same final amount as deposits of $4000 at the end of each 6 month period for 10 years at 4% compounded semiannually?

Determine the truth value- washington was assassinated : Write the following compound statements in symbolic form, then use your knowledge of the historical events referred to by the simple statements to determine the truth value of the compound statements.- It is not the case that either Alexander the ..

User Account

All Pages