What is the “critical path” when drawing an activity-on-node network diagram that doesn't converge?

Question

I'm studying for a software engineering final that covers project management, and am having a little bit of trouble with actually drawing network diagrams. The problem is, I've followed the table below and drawn a network diagram, but every example I've seen online, everything always converges into one final node.

Source Table

My Diagram

Note: I haven't added numbers to nodes.

Assuming the diagram's actually correct, I'm guessing the critical path is just the branch it would take the longest amount of time to traverse?

Answer 1

I hope this will help, I am currently studying these things as well; so, for what it's worth, this is what I can derive from speaking with PMPs I know and reading the PMBOK.

The critical path is a path generated by Finish-to-Start dependencies from one task to the next - resulting in a happy-path (everything went right) minimum project duration. So, if we assume all the tasks in the table and their predecessors are Finish-to-Start you seem good in drawing your chart.

Now, given that a project is defined as having a defined beginning and end, we could add a "virtual" node/task - wrapping up the project which has a Finish-to-Start dependency with the "final" node(s), with the path of the longest duration (as you may find your example has multiple paths resulting in the same total duration), in your diagram. So, if any of the tasks on those path(s) take longer than estimated - the further out our final node gets - critical path(s). For paths in your diagram that are shorter than the longest duration, there is an assumed Finish-to-Finish relationship from the final task on that path to the final "virtual" node in your diagram - because the project can't finish until all nodes/tasks are complete, but we have wiggle room for them to take longer than estimated (task M, for example) without effecting the total project duration.

In a nutshell, just as there is no task "0" for the first node in your graph - it is assumed to be the impetus for all other nodes - there is a node "n + 1" at the end of the project, which is where we tie a bow around the project. In the case of software engineering this might be the beginning of a new project - "Finish development - Begin preparing for marketing and release"...it's just not explicitly named in the data set.

Answer 2

Project Management Answer

Analysis

The critical path is, by definition, the longest path between two nodes. Wikipedia says (emphasis and italics mine):

CPM calculates the longest path of planned activities to logical end points or to the end of the project, and the earliest and latest that each activity can start and finish without making the project longer.

To complicate your question further, it also says:

A project can have several, parallel, near critical paths; and some or all of the tasks could have 'free float' and/or 'total float'. An additional parallel path through the network with the total durations shorter than the critical path is called a sub-critical or non-critical path. Activities on sub-critical paths have no drag, as they are not extending the project's duration.

In common usage, an activity-on-node diagram is generally expected to define real or virtual nodes for the starting and ending states. These nodes often represent project initiation and project closing, but integration or delivery (or even other terminal activities) might be the right endpoints for certain diagrams. In any case, you can certainly add "start" and "end" nodes when needed. For example:

However, if used as an activity diagram with multiple end points and parallel or near-critical paths, you can still use CPM to measure the longest distance between any two nodes in the diagram, so it's not inherently necessary that all paths converge.

Recommendations

It's not possible to know what the test or teacher considers the "correct" answer to be, but here are two possible solutions to your problem.

1. Add real or virtual nodes to represent the start and end of your project. The critical path is then the longest distance between the root node and the terminal node of your diagram.
2. Identify the root and terminal nodes for a given activity. The critical path is then the longest distance between the start and end of the activity.

In the real world, I would generally opt for the first method, but the second one could certainly be valid for some use cases. Your mileage may vary.

Note: Stop reading here unless you're a programmer!

---

Programming the Answer

Diagramming the Recommended Solution

Given your input data, and given my recommendations above, I'd suggest the following solution using Graphviz. Most people can skip this section of the answer, but it's here to document how to create such a graph by mapping the tasks and predecessors from the source table into code, which then generates your critical path diagram.

DOT Input File

The following contents should be stored in a DOT file named cpm.dot for compatibility with the subsequent examples.

digraph cpm {
    // predecessor -> task [label=duration]
    A -> C [label="5"];
    B -> D [label="1"];
    B -> E [label="1"];
    D -> F [label="6"];
    E -> G [label="4"];
    F -> H [label="2"];
    G -> I [label="1"];
    G -> J [label="1"];
    I -> K [label="3"];
    J -> L [label="3"];
    C -> M [label="1"];
    M -> N [label="1"];

    // virtual start & end nodes
    Start -> A, B;
    H, K, L, N -> End;
}

Create Graph from Input File

Generate cpm.png from the DOT file using Graphviz:

dot -Grankdir=LR -Tpng cpm.dot > cpm.png

Resulting Activity-on-Node Digraph