Gantt Critical Path with Kahn's Algorithm: Forward and Backward Pass

The critical path isn't just the longest sequence. It's the chain of tasks where any delay delays the entire project. Finding it requires topological sort — not just a greedy walk.

A Gantt chart with task dependencies has to answer one question visually: which tasks, if delayed, push the project end date? That's the critical path. The naive approach — find the longest chain by walking the dependency graph — fails when there are parallel paths. You need topological order first.

kui-react's Gantt component computes this in a useCriticalPath hook using Kahn's algorithm for topological sort, then a forward/backward pass for earliest/latest start times.

The Data Model

interface GanttTask {
  id: string;
  label: string;
  start: Date;
  end: Date;
  dependencies?: string[];  // ids of tasks that must finish before this starts
}

A task can depend on multiple predecessors. The dependency graph is a DAG (directed acyclic graph) — no cycles, because a task can't depend on itself or on its own successors.

Step 1: Build the Adjacency List

function buildGraph(tasks: GanttTask[]): {
  adj: Map<string, string[]>;
  inDegree: Map<string, number>;
} {
  const adj = new Map<string, string[]>();
  const inDegree = new Map<string, number>();

  for (const task of tasks) {
    if (!adj.has(task.id)) adj.set(task.id, []);
    if (!inDegree.has(task.id)) inDegree.set(task.id, 0);
  }

  for (const task of tasks) {
    for (const dep of task.dependencies ?? []) {
      // dep → task.id (dep must finish before task starts)
      adj.get(dep)!.push(task.id);
      inDegree.set(task.id, (inDegree.get(task.id) ?? 0) + 1);
    }
  }

  return { adj, inDegree };
}

inDegree tracks how many predecessors each task has. A task with inDegree = 0 has no dependencies — it can start immediately.

Step 2: Kahn's Topological Sort

function topoSort(
  tasks: GanttTask[],
  adj: Map<string, string[]>,
  inDegree: Map<string, number>,
): string[] {
  const queue: string[] = [];
  const order: string[] = [];

  // Seed: all tasks with no dependencies
  for (const task of tasks) {
    if ((inDegree.get(task.id) ?? 0) === 0) {
      queue.push(task.id);
    }
  }

  while (queue.length > 0) {
    const current = queue.shift()!;
    order.push(current);

    for (const neighbor of adj.get(current) ?? []) {
      const newDegree = (inDegree.get(neighbor) ?? 0) - 1;
      inDegree.set(neighbor, newDegree);
      if (newDegree === 0) queue.push(neighbor);
    }
  }

  if (order.length !== tasks.length) {
    // Cycle detected — return partial order
    console.warn('[Gantt] Cycle detected in task dependencies');
    return order;
  }

  return order;
}

Kahn's algorithm processes tasks in layers. Each time a task is removed from the queue, its outgoing edges are "cut" — successor in-degrees drop by one. When a successor reaches inDegree = 0, it's added to the queue.

The cycle detection: if order.length !== tasks.length, some tasks were never added to the queue because their in-degree never reached zero. That means a cycle exists. Instead of throwing, it returns the partial order and logs a warning — the Gantt still renders, just without critical path highlighting for the cyclic tasks.

Step 3: Forward Pass — Earliest Finish

function forwardPass(
  tasks: GanttTask[],
  order: string[],
  taskMap: Map<string, GanttTask>,
): Map<string, number> {
  // Values are timestamps (ms since epoch)
  const earliestFinish = new Map<string, number>();

  for (const id of order) {
    const task = taskMap.get(id)!;
    const duration = task.end.getTime() - task.start.getTime();

    const predFinishes = (task.dependencies ?? []).map(
      (dep) => earliestFinish.get(dep) ?? task.start.getTime(),
    );

    const earliestStart =
      predFinishes.length > 0
        ? Math.max(...predFinishes)
        : task.start.getTime();

    earliestFinish.set(id, earliestStart + duration);
  }

  return earliestFinish;
}

The topological order guarantees that when we process a task, all its predecessors have already been processed — their earliestFinish is in the map. So Math.max(...predFinishes) finds the binding constraint: the last predecessor to finish.

duration is computed from the task's own start/end, not from any scheduling. The task knows how long it takes; the algorithm determines when it can start.

Step 4: Backward Pass — Latest Start Without Delay

function backwardPass(
  tasks: GanttTask[],
  order: string[],
  taskMap: Map<string, GanttTask>,
  earliestFinish: Map<string, number>,
): Map<string, number> {
  const projectEnd = Math.max(...Array.from(earliestFinish.values()));
  const latestStart = new Map<string, number>();

  // Process in reverse topological order
  for (const id of [...order].reverse()) {
    const task = taskMap.get(id)!;
    const duration = task.end.getTime() - task.start.getTime();

    // Find successors of this task
    const successors = tasks.filter((t) =>
      t.dependencies?.includes(id)
    );

    if (successors.length === 0) {
      // No successors — can start as late as projectEnd - duration
      latestStart.set(id, projectEnd - duration);
    } else {
      const successorLatestStarts = successors.map(
        (s) => latestStart.get(s.id) ?? projectEnd,
      );
      latestStart.set(id, Math.min(...successorLatestStarts) - duration);
    }
  }

  return latestStart;
}

The backward pass answers: what's the latest this task can start without pushing the project end date? Tasks with no successors can start as late as projectEnd - duration. Tasks with successors must finish before their earliest successor starts.

Step 5: Float and Critical Path

export function useCriticalPath(tasks: GanttTask[]): Set<string> {
  return useMemo(() => {
    if (tasks.length === 0) return new Set();

    const taskMap = new Map(tasks.map((t) => [t.id, t]));
    const { adj, inDegree } = buildGraph(tasks);
    const order = topoSort(tasks, adj, inDegree);

    const earliestFinish = forwardPass(tasks, order, taskMap);
    const latestStart = backwardPass(tasks, order, taskMap, earliestFinish);

    const criticalIds = new Set<string>();

    for (const task of tasks) {
      const ef = earliestFinish.get(task.id) ?? 0;
      const ls = latestStart.get(task.id) ?? 0;
      const duration = task.end.getTime() - task.start.getTime();

      const earliestStart = ef - duration;
      const float = ls - earliestStart;

      if (Math.abs(float) < 1000) {  // < 1 second tolerance
        criticalIds.add(task.id);
      }
    }

    return criticalIds;
  }, [tasks]);
}

Float = Latest Start − Earliest Start. A task on the critical path has zero float — it cannot be delayed at all. The < 1000ms tolerance handles floating-point rounding in date arithmetic.

The hook returns a Set<string> of task IDs. The Gantt renderer checks criticalIds.has(task.id) and applies a different color to critical tasks and their connecting dependency arrows.

Rendering the Critical Path

function GanttBar({ task, criticalIds }: { task: GanttTask; criticalIds: Set<string> }) {
  const isCritical = criticalIds.has(task.id);

  return (
    <div
      className={cn(
        'gantt-bar',
        isCritical ? 'bg-error border-error' : 'bg-primary border-primary',
      )}
      style={{
        left: `${computeLeftPercent(task.start)}%`,
        width: `${computeWidthPercent(task.start, task.end)}%`,
      }}
    >
      {task.label}
    </div>
  );
}

Dependency arrows between tasks are also highlighted — if both the source and target are critical, the arrow gets the critical path color.

Why Not Just Find the Longest Path?

A greedy longest-path walk works for simple chains but breaks with parallel paths that converge. Consider:

A(3d) → C(2d)
B(5d) → C(2d)

Task C depends on both A and B. The longest path ending at C is B → C (7 days total). Kahn's + forward pass computes this correctly because it processes C only after both A and B are done, then takes Math.max(A.earliestFinish, B.earliestFinish) as C's earliest start.

A greedy walk might process A first, compute C's earliest start from A, then miss that B is actually the binding constraint. Topological order guarantees the right evaluation sequence.

Trade-offs

The backward pass has an O(N²) inner loop — for each task, it scans all tasks to find successors. For a Gantt with hundreds of tasks this becomes noticeable. A precomputed reverse adjacency list (reverseAdj) would drop this to O(N + E).

useMemo with [tasks] reruns on any task array reference change. If tasks are computed inline in the parent component, this memo never actually caches. The tasks array should be stable — memoized at the parent level.

Math.abs(float) < 1000 is a tolerance hack for date arithmetic rounding. A cleaner solution would work in integer days rather than milliseconds to avoid floating-point issues entirely.

Business Impact

Critical path visibility matters for project-based client work. When a client asks "what do I need to prioritize to not miss the deadline?", the answer is the critical path. Making it visually obvious — not buried in a tooltip or a separate report — changes the conversation from reactive to proactive.

For construction, engineering, and software project management tools, critical path is the core feature. Getting the algorithm right means the Gantt is analytically useful, not just a pretty chart.

Something to Try

If you have a task list with dependencies, compute the critical path before rendering. The forward/backward pass is about 50 lines. Add a float column to your task data structure — you'll immediately see which tasks have scheduling slack and which don't. That insight alone is worth the implementation cost.