Is there any difference between critical path and longest path in DAG?

Question

In every book I looked, they say that critical and longest path are the same. The problem is that, on critical path all activities has to be a critical ones. If I was searching for longest path, I wouldn't be paying any attention on whether activities are or aren't critical. Or I don't get something?

Answer 1

consider a graph modeling a project composed of a set of serializable, partially interdependent activities, where the activities are represented by edges and the interdependence by nodes such that 2 edges e1, e2 are incident iff the e1 activity must be completed before the activity e2 can start. assume 2 special vertices s,t representing the start and the end of a project, resp.

in such a model, the critical path describes a maximal sequence of activities that cannot be parallelized wrt each other.

its name stems from the fact that any delay in precisely one of the activities on the critical path necessarily delays the complete project while for all other activities there is some buffer time available.

in particular the critical path does not necessarily match those activities which are essential for an overall success to the project.

the critical path corresponds to the longest path between s, t in the graph.

the critical path need not be unique, of course.

Answer 2

From http://en.wikipedia.org/wiki/Longest_path_problem

The critical path method for scheduling a set of activities involves the construction of a directed acyclic graph in which the vertices represent project milestones and the edges represent activities that must be performed after one milestone and before another; each edge is weighted by an estimate of the amount of time the corresponding activity will take to complete. In such a graph, the longest path from the first milestone to the last one is the critical path, which describes the total time for completing the project.

They cite Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms (4th ed.), Addison-Wesley Professional, pp. 661–666.