A critical path in a weighted, directed, acyclic graph is the path with the greatest

Chapter 28, Problem 22

(choose chapter or problem)

A critical path in a weighted, directed, acyclic graph is the path with the greatest weight. Lets assume that all edge weights are positive. Give each vertex a value equal to the weight of a path to that vertex. Initially, each vertexs 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 edges source vertex. Compare the sum with the value of the edges 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.