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.
