Critical Path Method

Every project has a path through its task dependencies that sets the floor on delivery time. Delay any task along that path, and the entire schedule slips by exactly the same amount. This is the critical path: the longest chain of dependent work from start to finish.

Critical Path Method (CPM) formalized this idea in the late 1950s as part of operations research, the same discipline that produced linear programming, queuing theory, and combinatorial optimization. The mathematics have not changed in six decades. What has changed is who extracts the dependency graph. Large language models can now parse a project description, identify tasks and precedence constraints, and serialize the result into formats like Mermaid that render directly in tools engineers already use.

This article defines the critical path, walks through a computed example, and shows how LLMs like Claude can automate dependency extraction for integration with GitHub Issues.

Roots in Operations Research

CPM emerged from two parallel efforts in the 1950s. Morgan Walker at DuPont and James Kelley at Remington Rand developed the method in 1957 for scheduling chemical plant maintenance shutdowns, where task durations were well-known from prior turnarounds. A year later, the U.S. Navy Special Projects Office created PERT (Program Evaluation and Review Technique) for the Polaris submarine-launched ballistic missile program, where R&D timelines were uncertain.

Both techniques model a project as a directed acyclic graph (DAG). Nodes represent tasks. Directed edges represent precedence constraints: task B cannot start until task A finishes. Each node carries a duration estimate. The critical path is the longest weighted path through this graph.

The distinction between the two methods matters. CPM assumes durations are deterministic point estimates. PERT treats them as probability distributions (optimistic, most likely, pessimistic) and propagates variance along paths. In practice, most modern scheduling tools use the CPM framework with point estimates and optional sensitivity analysis rather than full PERT distributions.

Defining the Critical Path

The critical path is the longest sequence of dependent tasks from a project's start to its end, measured by total duration. Three properties follow from this definition.

First, the critical path determines the minimum project duration. No amount of parallelism or resource reallocation can shorten the schedule below this floor.

Second, every critical task has zero total float (also called slack). Delay a critical task by one day, and the project end date moves by one day.

Third, non-critical tasks have positive float. They can slip without affecting the deadline. Float is the difference between a task's latest allowable start time and its earliest possible start time.

A project can have multiple critical paths of equal length. When this happens, the schedule is more fragile: a delay on any of those paths pushes the deadline. Conversely, tasks with large float represent scheduling flexibility. Resources can shift away from high-float tasks toward critical ones without affecting the end date.

A Worked Example

Consider a team shipping a user authentication feature. The work decomposes into eight tasks:

• T1: Design auth flow (3 days): no dependencies
• T2: Database schema (2 days): depends on T1
• T3: OAuth provider integration (4 days): depends on T1
• T4: Login UI (3 days): depends on T1
• T5: API integration tests (2 days): depends on T2, T3
• T6: End-to-end tests (2 days): depends on T4, T5
• T7: Security audit (3 days): depends on T5
• T8: Deploy to production (1 day): depends on T6, T7

After T1 completes, three streams of work can run in parallel: database (T2), OAuth (T3), and frontend (T4). The dependency structure determines which parallel streams constrain the schedule and which have room to slip.

Computing the Critical Path

The CPM algorithm makes two passes over the graph. The forward pass computes each task's earliest possible start and finish times by traversing the graph in topological order. The backward pass computes latest allowable times by traversing in reverse from the project end date. The difference between latest and earliest start is the float.

The following code builds the dependency graph, runs both passes, and renders the result. Critical tasks (zero float) appear in red; non-critical tasks in blue with their float annotated.

Show Python source

import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import networkx as nx

FT_BG       = '#FFF1E5'
FT_OXFORD   = '#0F5499'
FT_TEAL     = '#0D7680'
FT_CLARET   = '#990F3D'

plt.rcParams.update({
    'figure.facecolor':  FT_BG,
    'axes.facecolor':    FT_BG,
    'savefig.facecolor': FT_BG,
    'font.family':       'sans-serif',
    'font.sans-serif':   ['Helvetica Neue', 'Arial', 'DejaVu Sans'],
    'font.size':          13,
    'text.color':        '#333333',
    'axes.labelcolor':   '#333333',
    'axes.spines.top':    False,
    'axes.spines.right':  False,
    'axes.spines.left':   False,
    'axes.spines.bottom': False,
})

# ── Task definitions ──
tasks = {
    'T1': {'label': 'Design\nAuth Flow', 'duration': 3},
    'T2': {'label': 'Database\nSchema',   'duration': 2},
    'T3': {'label': 'OAuth\nProvider',    'duration': 4},
    'T4': {'label': 'Login UI',           'duration': 3},
    'T5': {'label': 'API Tests',          'duration': 2},
    'T6': {'label': 'E2E Tests',          'duration': 2},
    'T7': {'label': 'Security\nAudit',    'duration': 3},
    'T8': {'label': 'Deploy',             'duration': 1},
}

deps = [
    ('T1', 'T2'), ('T1', 'T3'), ('T1', 'T4'),
    ('T2', 'T5'), ('T3', 'T5'),
    ('T4', 'T6'), ('T5', 'T6'), ('T5', 'T7'),
    ('T6', 'T8'), ('T7', 'T8'),
]

G = nx.DiGraph()
for tid, info in tasks.items():
    G.add_node(tid, duration=info['duration'])
G.add_edges_from(deps)

# ── Forward pass: earliest start / finish ──
topo = list(nx.topological_sort(G))
ES, EF = {}, {}
for t in topo:
    ES[t] = max([EF[p] for p in G.predecessors(t)], default=0)
    EF[t] = ES[t] + tasks[t]['duration']

# ── Backward pass: latest start / finish ──
project_end = max(EF.values())
LS, LF = {}, {}
for t in reversed(topo):
    LF[t] = min([LS[s] for s in G.successors(t)], default=project_end)
    LS[t] = LF[t] - tasks[t]['duration']

# ── Float and critical path ──
total_float = {t: LS[t] - ES[t] for t in tasks}
critical = {t for t in tasks if total_float[t] == 0}
critical_edges = {(u, v) for u, v in deps
                  if u in critical and v in critical and ES[v] == EF[u]}

# ── Layout (manual positions for clean left-to-right flow) ──
pos = {
    'T1': (0.0, 0.50),
    'T2': (1.5, 0.85),
    'T3': (1.5, 0.50),
    'T4': (1.5, 0.15),
    'T5': (3.0, 0.67),
    'T6': (4.2, 0.25),
    'T7': (4.2, 0.75),
    'T8': (5.5, 0.50),
}

fig, ax = plt.subplots(figsize=(10, 5.5))

# Non-critical edges
nc_edges = [e for e in deps if e not in critical_edges]
nx.draw_networkx_edges(G, pos, edgelist=nc_edges, edge_color='#BBBBBB',
                       width=1.5, arrows=True, arrowsize=15,
                       arrowstyle='-|>', ax=ax,
                       connectionstyle='arc3,rad=0.05')

# Critical edges
c_edges = [e for e in deps if e in critical_edges]
nx.draw_networkx_edges(G, pos, edgelist=c_edges, edge_color=FT_CLARET,
                       width=2.5, arrows=True, arrowsize=18,
                       arrowstyle='-|>', ax=ax,
                       connectionstyle='arc3,rad=0.05')

# Nodes
colors = [FT_CLARET if n in critical else FT_OXFORD for n in G.nodes()]
nx.draw_networkx_nodes(G, pos, node_size=2400, node_color=colors,
                       edgecolors='white', linewidths=2, ax=ax)

# Labels
labels = {}
for tid in tasks:
    d = tasks[tid]['duration']
    labels[tid] = f"{tasks[tid]['label']}\n({d}d)"
nx.draw_networkx_labels(G, pos, labels, font_size=7.5, font_color='white',
                        font_weight='bold', ax=ax)


fig.text(0.50, 0.97, 'Critical Path: User Authentication Feature',
         ha='center', fontsize=16, fontweight='bold', color='#333333')
fig.text(0.50, 0.935,
         f'Minimum duration: {project_end} days  \u00b7  Critical tasks highlighted in red',
         ha='center', fontsize=11, color='#666666')
fig.text(0.02, 0.01, 'Source: Philip Jama via pjama.github.io',
         fontsize=9, color='#999999', ha='left')

ax.set_xlim(-0.6, 6.1)
ax.set_ylim(-0.15, 1.10)
ax.axis('off')

fig.tight_layout(rect=[0, 0.03, 1, 0.92])
fig.savefig('critical_path_dag.png', dpi=150, facecolor=FT_BG, bbox_inches='tight')

The critical path runs T1 → T3 → T5 → T7 → T8, totaling 13 days. T3 (OAuth provider, 4 days) is the longest individual task and sits squarely on the critical path; any delay there propagates directly to the deadline. T4 (Login UI) has 4 days of float: the frontend work could start late or overrun without affecting the schedule. T6 (end-to-end tests) has just 1 day of float, which is thin enough to warrant monitoring.

LLMs as Dependency Extractors

The hardest part of CPM is not the algorithm. It is building the dependency graph. In practice, task relationships live in the heads of engineers and project managers, scattered across meeting notes, ticket descriptions, and Slack threads. Extracting a complete, correct graph from this informal knowledge is the bottleneck.

Large language models are well-suited to this kind of structured extraction. Given a natural-language project description, Claude can identify discrete tasks, infer precedence constraints from contextual cues ("after the schema is finalized," "once tests pass"), and serialize the result as a dependency graph.

Mermaid as the Interchange Format

Mermaid is a lightweight diagramming syntax that renders in GitHub, GitLab, Notion, and Confluence without plugins. Asking an LLM to produce Mermaid rather than raw JSON or adjacency lists has a practical advantage: the output is both machine-readable and human-readable, and it renders as a visual diagram wherever markdown is displayed.

Given the project description from the previous section, Claude produces the following Mermaid flowchart with the critical path highlighted:

graph LR
    T1["Design Auth Flow (3d)"] --> T2["Database Schema (2d)"]
    T1 --> T3["OAuth Provider (4d)"]
    T1 --> T4["Login UI (3d)"]
    T2 --> T5["API Tests (2d)"]
    T3 --> T5
    T4 --> T6["E2E Tests (2d)"]
    T5 --> T6
    T5 --> T7["Security Audit (3d)"]
    T6 --> T8["Deploy (1d)"]
    T7 --> T8

    style T1 fill:#990F3D,color:#fff
    style T3 fill:#990F3D,color:#fff
    style T5 fill:#990F3D,color:#fff
    style T7 fill:#990F3D,color:#fff
    style T8 fill:#990F3D,color:#fff

The style directives highlight critical tasks in the same claret used in the rendered visualization. On GitHub, this code block renders as an interactive diagram when placed inside a fenced code block tagged mermaid in any issue, PR, or wiki page.

Integration with GitHub Issues

GitHub Issues provides a natural home for CPM when the goal is to keep planning context alongside the code. Each task maps to an issue. Dependencies are expressed through cross-references in the issue body ("Blocked by #12") or via GitHub's sub-issue tracking. Milestones mark delivery targets.

Claude Code can read a repository's full issue state through the gh CLI, making a lightweight CPM workflow possible without leaving the platform. Given a milestone, Claude reads all linked issues, parses the dependency structure from cross-references and labels, computes the forward and backward pass, and posts the resulting Mermaid diagram as a comment on the milestone tracking issue.

Duration estimates can live in issue labels (duration:3d) or in a structured field in the issue body. The convention matters less than consistency: Claude needs a parseable signal for each task's estimated duration and a reliable pattern for expressing "this task is blocked by that task."

For teams using Linear, the same pattern works through Claude's MCP (Model Context Protocol) integration. Linear's API exposes issue dependencies and project structure as first-class objects, which Claude can query directly. The advantage of GitHub is consolidation: the critical path diagram lives in the same repository as the code, visible to anyone with access, versioned alongside the work it describes.

CPM reduces project scheduling to a graph problem: find the longest path in a DAG. The mathematics are elementary; the historical difficulty has always been in extracting an accurate dependency graph from human knowledge and keeping it current as plans evolve. LLMs lower the extraction cost from a manual modeling exercise to a conversational query. When that query is embedded in the same issue tracker where tasks already live, the gap between informal planning and formal schedule analysis closes substantially.

The same pattern of LLM-generated Mermaid syntax extends beyond project schedules. The Books project ↗ uses this approach as its foundation: an LLM produces a structured outline of a book's conceptual hierarchy, serialized as a graph, which is then parsed and rendered as a color-coded knowledge tree. Once an LLM can reliably produce a parseable graph description, the downstream tooling (rendering, analysis, querying) follows naturally.

The directed acyclic graph at the heart of CPM is the same structure that appears in causal inference and knowledge graphs: a formalism where direction encodes precedence and cycles are forbidden. The analytical tools, from topological sorting to longest-path algorithms, transfer directly.