DP on DAGs

Introduction

A directed acyclic graph (DAG) is a graph where edges point in one direction and there are no cycles — no way to follow edges and arrive back where you started. That sounds like a restriction, but it is actually a superpower.

Because there are no cycles, a DAG has a topological order: a way to list every node so that all edges point forward — from earlier entries in the list to later ones. Think of it like a schedule: task B can only start after task A finishes, and the topological order simply lists tasks in a valid execution sequence.

Once you have that order, dynamic programming becomes trivial. To compute the optimal value at any node, you only need to look at the nodes that come before it — and those have already been processed. A single left-to-right sweep over the topologically sorted nodes solves the entire problem.

This is not a niche trick. Shortest paths in a DAG, longest paths (critical path scheduling), the number of paths between two nodes, the probability of reaching a target — all collapse to the same linear scan. The key insight, proven by the structure of DAGs themselves, is that optimal substructure + topological order = one pass.

Try It

The graph below has seven nodes. Every edge has a weight (shown on the arrow). Click Topological DP to watch the algorithm assign the shortest distance from node S to every other node in one left-to-right sweep over the topological order.

<p class="hint">A directed acyclic graph (DAG) with 7 nodes and weighted edges. Click <b>Topological DP</b> to find shortest distances from S in one left-to-right sweep. Click <b>Reset</b> to start over.</p>
<canvas id="dag" width="560" height="320"></canvas>
<div class="status" id="status">Press Topological DP to run the algorithm.</div>
<div class="btns">
  <button id="run" type="button">Topological DP</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; background: #f4f7fa; border-radius: 10px; max-width: 100%; border: 1px solid #dce3ea; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0 .4rem; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ────────────────────────────────────────────────────────────────────────────────
// Nodes: S, A, B, C, D, E, T
// Topological order (left to right): S, A, B, C, D, E, T
// Edges (from, to, weight) — DAG, no back-edges.
const NODES = [
  { id: 'S', x: 50,  y: 160 },
  { id: 'A', x: 155, y: 70  },
  { id: 'B', x: 155, y: 250 },
  { id: 'C', x: 280, y: 160 },
  { id: 'D', x: 370, y: 70  },
  { id: 'E', x: 370, y: 250 },
  { id: 'T', x: 490, y: 160 }
];
const EDGES = [
  { from: 'S', to: 'A', w: 4 },
  { from: 'S', to: 'B', w: 2 },
  { from: 'A', to: 'C', w: 3 },
  { from: 'B', to: 'C', w: 6 },
  { from: 'B', to: 'E', w: 5 },
  { from: 'C', to: 'D', w: 2 },
  { from: 'C', to: 'E', w: 4 },
  { from: 'D', to: 'T', w: 1 },
  { from: 'E', to: 'T', w: 3 }
];
// Topological order (hardcoded for this fixed DAG):
const TOPO = ['S','A','B','C','D','E','T'];

const canvas = document.getElementById('dag');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// ── State ────────────────────────────────────────────────────────────────────────────
let dist = {};        // shortest distance from S
let prev = {};        // predecessor in optimal path
let step = 0;         // which node in TOPO we've processed so far
let settled = new Set();
let activeEdges = []; // edges highlighted in current step
let optPath = [];     // edges on final optimal S→T path

function init() {
  dist = {}; prev = {}; step = 0; settled = new Set();
  activeEdges = []; optPath = [];
  NODES.forEach(n => { dist[n.id] = n.id === 'S' ? 0 : Infinity; prev[n.id] = null; });
}
init();

// ── Drawing helpers ─────────────────────────────────────────────────────────────────────────
function nodeById(id) { return NODES.find(n => n.id === id); }

function drawArrow(x1, y1, x2, y2, color, lw) {
  const R = 22; // node radius to back off from
  const dx = x2 - x1, dy = y2 - y1, len = Math.hypot(dx, dy);
  const ux = dx / len, uy = dy / len;
  // Start / end points backed off by node radius
  const sx = x1 + ux * R, sy = y1 + uy * R;
  const ex = x2 - ux * (R + 6), ey = y2 - uy * (R + 6);
  ctx.save();
  ctx.strokeStyle = color;
  ctx.lineWidth = lw;
  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.stroke();
  // Arrowhead
  const angle = Math.atan2(uy, ux);
  ctx.fillStyle = color;
  ctx.beginPath();
  ctx.moveTo(ex + ux * 6, ey + uy * 6);
  ctx.lineTo(ex - Math.cos(angle - 0.45) * 9, ey - Math.sin(angle - 0.45) * 9);
  ctx.lineTo(ex - Math.cos(angle + 0.45) * 9, ey - Math.sin(angle + 0.45) * 9);
  ctx.closePath();
  ctx.fill();
  ctx.restore();
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  EDGES.forEach(e => {
    const a = nodeById(e.from), b = nodeById(e.to);
    const isOpt = optPath.some(p => p.from === e.from && p.to === e.to);
    const isActive = activeEdges.some(p => p.from === e.from && p.to === e.to);
    const color = isOpt ? '#0a7d33' : isActive ? '#e07b00' : '#8fa6be';
    const lw = isOpt ? 2.8 : isActive ? 2.2 : 1.4;
    drawArrow(a.x, a.y, b.x, b.y, color, lw);

    // Weight label
    const mx = (a.x + b.x) / 2, my = (a.y + b.y) / 2;
    const nx = -(b.y - a.y) / Math.hypot(b.x - a.x, b.y - a.y);
    const ny =  (b.x - a.x) / Math.hypot(b.x - a.x, b.y - a.y);
    const lx = mx + nx * 14, ly = my + ny * 14;
    ctx.save();
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.fillStyle = isOpt ? '#0a7d33' : '#445566';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(e.w, lx, ly);
    ctx.restore();
  });

  // Draw nodes
  NODES.forEach(n => {
    const isSettled = settled.has(n.id);
    const isCurrent = TOPO[step - 1] === n.id && step > 0 && step <= TOPO.length;
    const isOnPath = optPath.length > 0 && (n.id === 'T' || optPath.some(p => p.from === n.id));

    ctx.save();
    ctx.beginPath();
    ctx.arc(n.x, n.y, 22, 0, Math.PI * 2);
    if (isOnPath && optPath.length > 0) {
      ctx.fillStyle = '#d4edda';
      ctx.strokeStyle = '#0a7d33';
      ctx.lineWidth = 2.5;
    } else if (isCurrent) {
      ctx.fillStyle = '#fff3cd';
      ctx.strokeStyle = '#e07b00';
      ctx.lineWidth = 2.5;
    } else if (isSettled) {
      ctx.fillStyle = '#dce8f5';
      ctx.strokeStyle = '#1d3557';
      ctx.lineWidth = 2;
    } else {
      ctx.fillStyle = '#fff';
      ctx.strokeStyle = '#8fa6be';
      ctx.lineWidth = 1.5;
    }
    ctx.fill(); ctx.stroke();

    // Node label
    ctx.font = 'bold 15px system-ui, sans-serif';
    ctx.fillStyle = isOnPath && optPath.length > 0 ? '#0a7d33' : isCurrent ? '#a05000' : '#1d3557';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(n.id, n.x, n.y - (isSettled || isCurrent ? 5 : 0));

    // Distance label
    if (dist[n.id] !== undefined) {
      const d = dist[n.id];
      ctx.font = '11px system-ui, sans-serif';
      ctx.fillStyle = '#2563a8';
      ctx.fillText(d === Infinity ? '∞' : d, n.x, n.y + 9);
    }
    ctx.restore();
  });
}

// ── Algorithm step ────────────────────────────────────────────────────────────────────────────
function runStep() {
  if (step >= TOPO.length) return false; // done
  const nodeId = TOPO[step];
  settled.add(nodeId);
  activeEdges = [];

  // Relax all edges FROM this node
  EDGES.filter(e => e.from === nodeId).forEach(e => {
    const newDist = dist[nodeId] + e.w;
    if (newDist < dist[e.to]) {
      dist[e.to] = newDist;
      prev[e.to] = nodeId;
    }
    activeEdges.push({ from: e.from, to: e.to });
  });
  step++;
  return true;
}

function buildOptPath() {
  // Trace back from T using prev[]
  optPath = [];
  let cur = 'T';
  while (prev[cur]) {
    optPath.push({ from: prev[cur], to: cur });
    cur = prev[cur];
  }
}

// ── Animated run ──────────────────────────────────────────────────────────────────────────────
let animTimer = null;
document.getElementById('run').addEventListener('click', function () {
  if (animTimer) return;
  this.disabled = true;
  document.getElementById('reset').disabled = true;

  function tick() {
    const more = runStep();
    draw();
    const nodeId = TOPO[step - 1];
    if (more && step < TOPO.length) {
      document.getElementById('status').textContent =
        fmt('Processing node %nodeId% (step %step% / %length%) — relaxing outgoing edges...', { nodeId: nodeId, step: step, length: TOPO.length });
      animTimer = setTimeout(tick, 800);
    } else if (more) {
      // Last node processed
      document.getElementById('status').textContent =
        fmt('Processing node %nodeId% (step %step% / %length%) — done!', { nodeId: nodeId, step: step, length: TOPO.length });
      animTimer = setTimeout(() => {
        activeEdges = [];
        buildOptPath();
        draw();
        const d = dist['T'];
        document.getElementById('status').textContent =
          fmt('Done! Shortest S → T = %d% (path highlighted in green). Every node visited exactly once — O(V+E).', { d: d });
        document.getElementById('status').className = 'status done';
        document.getElementById('reset').disabled = false;
        animTimer = null;
      }, 800);
    }
  }
  tick();
});

document.getElementById('reset').addEventListener('click', function () {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  document.getElementById('run').disabled = false;
  this.disabled = false;
  document.getElementById('status').textContent = 'Press Topological DP to run the algorithm.';
  document.getElementById('status').className = 'status';
  init();
  draw();
});

draw();

// ── Node verification (for node script) ────────────────────────────────────────────
// Run the full algorithm headlessly and log results for test verification.
(function verify() {
  // Reset state
  const d2 = {}; const p2 = {};
  NODES.forEach(n => { d2[n.id] = n.id === 'S' ? 0 : Infinity; p2[n.id] = null; });
  TOPO.forEach(nodeId => {
    EDGES.filter(e => e.from === nodeId).forEach(e => {
      if (d2[nodeId] + e.w < d2[e.to]) { d2[e.to] = d2[nodeId] + e.w; p2[e.to] = nodeId; }
    });
  });
  const results = Object.entries(d2).map(([k,v]) => k+'='+v).join(', ');
  if (typeof console !== 'undefined') console.log('Topo DP distances:', results);
})();

<p class="hint">A directed acyclic graph (DAG) with 7 nodes and weighted edges. Click <b>Topological DP</b> to find shortest distances from S in one left-to-right sweep. Click <b>Reset</b> to start over.</p>
<canvas id="dag" width="560" height="320"></canvas>
<div class="status" id="status">Press Topological DP to run the algorithm.</div>
<div class="btns">
  <button id="run" type="button">Topological DP</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; background: #f4f7fa; border-radius: 10px; max-width: 100%; border: 1px solid #dce3ea; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0 .4rem; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ────────────────────────────────────────────────────────────────────────────────
// Nodes: S, A, B, C, D, E, T
// Topological order (left to right): S, A, B, C, D, E, T
// Edges (from, to, weight) — DAG, no back-edges.
const NODES = [
  { id: 'S', x: 50,  y: 160 },
  { id: 'A', x: 155, y: 70  },
  { id: 'B', x: 155, y: 250 },
  { id: 'C', x: 280, y: 160 },
  { id: 'D', x: 370, y: 70  },
  { id: 'E', x: 370, y: 250 },
  { id: 'T', x: 490, y: 160 }
];
const EDGES = [
  { from: 'S', to: 'A', w: 4 },
  { from: 'S', to: 'B', w: 2 },
  { from: 'A', to: 'C', w: 3 },
  { from: 'B', to: 'C', w: 6 },
  { from: 'B', to: 'E', w: 5 },
  { from: 'C', to: 'D', w: 2 },
  { from: 'C', to: 'E', w: 4 },
  { from: 'D', to: 'T', w: 1 },
  { from: 'E', to: 'T', w: 3 }
];
// Topological order (hardcoded for this fixed DAG):
const TOPO = ['S','A','B','C','D','E','T'];

const canvas = document.getElementById('dag');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// ── State ────────────────────────────────────────────────────────────────────────────
let dist = {};        // shortest distance from S
let prev = {};        // predecessor in optimal path
let step = 0;         // which node in TOPO we've processed so far
let settled = new Set();
let activeEdges = []; // edges highlighted in current step
let optPath = [];     // edges on final optimal S→T path

function init() {
  dist = {}; prev = {}; step = 0; settled = new Set();
  activeEdges = []; optPath = [];
  NODES.forEach(n => { dist[n.id] = n.id === 'S' ? 0 : Infinity; prev[n.id] = null; });
}
init();

// ── Drawing helpers ─────────────────────────────────────────────────────────────────────────
function nodeById(id) { return NODES.find(n => n.id === id); }

function drawArrow(x1, y1, x2, y2, color, lw) {
  const R = 22; // node radius to back off from
  const dx = x2 - x1, dy = y2 - y1, len = Math.hypot(dx, dy);
  const ux = dx / len, uy = dy / len;
  // Start / end points backed off by node radius
  const sx = x1 + ux * R, sy = y1 + uy * R;
  const ex = x2 - ux * (R + 6), ey = y2 - uy * (R + 6);
  ctx.save();
  ctx.strokeStyle = color;
  ctx.lineWidth = lw;
  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.stroke();
  // Arrowhead
  const angle = Math.atan2(uy, ux);
  ctx.fillStyle = color;
  ctx.beginPath();
  ctx.moveTo(ex + ux * 6, ey + uy * 6);
  ctx.lineTo(ex - Math.cos(angle - 0.45) * 9, ey - Math.sin(angle - 0.45) * 9);
  ctx.lineTo(ex - Math.cos(angle + 0.45) * 9, ey - Math.sin(angle + 0.45) * 9);
  ctx.closePath();
  ctx.fill();
  ctx.restore();
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  EDGES.forEach(e => {
    const a = nodeById(e.from), b = nodeById(e.to);
    const isOpt = optPath.some(p => p.from === e.from && p.to === e.to);
    const isActive = activeEdges.some(p => p.from === e.from && p.to === e.to);
    const color = isOpt ? '#0a7d33' : isActive ? '#e07b00' : '#8fa6be';
    const lw = isOpt ? 2.8 : isActive ? 2.2 : 1.4;
    drawArrow(a.x, a.y, b.x, b.y, color, lw);

    // Weight label
    const mx = (a.x + b.x) / 2, my = (a.y + b.y) / 2;
    const nx = -(b.y - a.y) / Math.hypot(b.x - a.x, b.y - a.y);
    const ny =  (b.x - a.x) / Math.hypot(b.x - a.x, b.y - a.y);
    const lx = mx + nx * 14, ly = my + ny * 14;
    ctx.save();
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.fillStyle = isOpt ? '#0a7d33' : '#445566';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(e.w, lx, ly);
    ctx.restore();
  });

  // Draw nodes
  NODES.forEach(n => {
    const isSettled = settled.has(n.id);
    const isCurrent = TOPO[step - 1] === n.id && step > 0 && step <= TOPO.length;
    const isOnPath = optPath.length > 0 && (n.id === 'T' || optPath.some(p => p.from === n.id));

    ctx.save();
    ctx.beginPath();
    ctx.arc(n.x, n.y, 22, 0, Math.PI * 2);
    if (isOnPath && optPath.length > 0) {
      ctx.fillStyle = '#d4edda';
      ctx.strokeStyle = '#0a7d33';
      ctx.lineWidth = 2.5;
    } else if (isCurrent) {
      ctx.fillStyle = '#fff3cd';
      ctx.strokeStyle = '#e07b00';
      ctx.lineWidth = 2.5;
    } else if (isSettled) {
      ctx.fillStyle = '#dce8f5';
      ctx.strokeStyle = '#1d3557';
      ctx.lineWidth = 2;
    } else {
      ctx.fillStyle = '#fff';
      ctx.strokeStyle = '#8fa6be';
      ctx.lineWidth = 1.5;
    }
    ctx.fill(); ctx.stroke();

    // Node label
    ctx.font = 'bold 15px system-ui, sans-serif';
    ctx.fillStyle = isOnPath && optPath.length > 0 ? '#0a7d33' : isCurrent ? '#a05000' : '#1d3557';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(n.id, n.x, n.y - (isSettled || isCurrent ? 5 : 0));

    // Distance label
    if (dist[n.id] !== undefined) {
      const d = dist[n.id];
      ctx.font = '11px system-ui, sans-serif';
      ctx.fillStyle = '#2563a8';
      ctx.fillText(d === Infinity ? '∞' : d, n.x, n.y + 9);
    }
    ctx.restore();
  });
}

// ── Algorithm step ────────────────────────────────────────────────────────────────────────────
function runStep() {
  if (step >= TOPO.length) return false; // done
  const nodeId = TOPO[step];
  settled.add(nodeId);
  activeEdges = [];

  // Relax all edges FROM this node
  EDGES.filter(e => e.from === nodeId).forEach(e => {
    const newDist = dist[nodeId] + e.w;
    if (newDist < dist[e.to]) {
      dist[e.to] = newDist;
      prev[e.to] = nodeId;
    }
    activeEdges.push({ from: e.from, to: e.to });
  });
  step++;
  return true;
}

function buildOptPath() {
  // Trace back from T using prev[]
  optPath = [];
  let cur = 'T';
  while (prev[cur]) {
    optPath.push({ from: prev[cur], to: cur });
    cur = prev[cur];
  }
}

// ── Animated run ──────────────────────────────────────────────────────────────────────────────
let animTimer = null;
document.getElementById('run').addEventListener('click', function () {
  if (animTimer) return;
  this.disabled = true;
  document.getElementById('reset').disabled = true;

  function tick() {
    const more = runStep();
    draw();
    const nodeId = TOPO[step - 1];
    if (more && step < TOPO.length) {
      document.getElementById('status').textContent =
        fmt('Processing node %nodeId% (step %step% / %length%) — relaxing outgoing edges...', { nodeId: nodeId, step: step, length: TOPO.length });
      animTimer = setTimeout(tick, 800);
    } else if (more) {
      // Last node processed
      document.getElementById('status').textContent =
        fmt('Processing node %nodeId% (step %step% / %length%) — done!', { nodeId: nodeId, step: step, length: TOPO.length });
      animTimer = setTimeout(() => {
        activeEdges = [];
        buildOptPath();
        draw();
        const d = dist['T'];
        document.getElementById('status').textContent =
          fmt('Done! Shortest S → T = %d% (path highlighted in green). Every node visited exactly once — O(V+E).', { d: d });
        document.getElementById('status').className = 'status done';
        document.getElementById('reset').disabled = false;
        animTimer = null;
      }, 800);
    }
  }
  tick();
});

document.getElementById('reset').addEventListener('click', function () {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  document.getElementById('run').disabled = false;
  this.disabled = false;
  document.getElementById('status').textContent = 'Press Topological DP to run the algorithm.';
  document.getElementById('status').className = 'status';
  init();
  draw();
});

draw();

// ── Node verification (for node script) ────────────────────────────────────────────
// Run the full algorithm headlessly and log results for test verification.
(function verify() {
  // Reset state
  const d2 = {}; const p2 = {};
  NODES.forEach(n => { d2[n.id] = n.id === 'S' ? 0 : Infinity; p2[n.id] = null; });
  TOPO.forEach(nodeId => {
    EDGES.filter(e => e.from === nodeId).forEach(e => {
      if (d2[nodeId] + e.w < d2[e.to]) { d2[e.to] = d2[nodeId] + e.w; p2[e.to] = nodeId; }
    });
  });
  const results = Object.entries(d2).map(([k,v]) => k+'='+v).join(', ');
  if (typeof console !== 'undefined') console.log('Topo DP distances:', results);
})();

Result

Console

Notice that each node is visited exactly once. As soon as the algorithm reaches a node, all its predecessors have already been settled — so it can immediately compute the optimal distance by scanning incoming edges. No priority queue, no re-relaxation: just a single pass over the sorted nodes, each processed in O(incoming edges) time, giving $O(V + E)$ total.

The Real Complexity

How fast is DP on a DAG, and why can't general graphs do the same?

Topological sort costs $O(V + E)$ — one DFS or a Kahn's algorithm BFS — and it is unique (up to ties among equally valid orderings) when the graph is a DAG.
The DP sweep also costs $O(V + E)$ : each node is processed once, and each edge is relaxed once. Total work is therefore $O(V + E)$ , which is optimal — you cannot solve shortest paths without at least reading every edge.
Compare with Dijkstra: on a general weighted graph with no negative edges, Dijkstra needs O((V + E) log V) for a binary heap. On a DAG it is unnecessary — topological order already guarantees no node is visited before all its predecessors.
Negative edges? No problem. Bellman-Ford needs $O(VE)$ to handle negative weights safely. On a DAG, topological order handles any weight, positive or negative, in linear time — because cycles are what make negative weights dangerous, and a DAG has none.
Longest path. On a general graph, longest path is NP-hard (it subsumes Hamiltonian path). On a DAG, negate all weights and run the same DP — still $O(V + E)$ . This is why project scheduling (critical path method, CPM) uses DAGs.

The secret is that the structure of a DAG eliminates the hard part. There is no search, no backtracking, no exponential explosion. The topological order is a certificate that every sub-problem is already solved before you need it.

Where It Matters

The "process nodes in topological order" pattern appears across computer science whenever there are dependencies:

Critical path scheduling (CPM / PERT): model a project as a DAG of tasks with durations. The longest path gives the minimum project duration. Used in construction, manufacturing, and software releases.
Build systems: Make, Bazel, and Ninja all represent source-file dependencies as DAGs and compile in topological order. A changed file triggers recompilation of all descendants — found by a reverse topological scan.
Sequence alignment (edit distance): the classic DP table for sequence alignment is a grid whose cells form a DAG (each cell depends only on the cell to the left, above, and diagonally). Filling it row by row is topological DP in disguise.
Probability and Bayesian networks: in a Bayesian network (a DAG of random variables), computing marginal probabilities by message-passing follows topological order. This is the backbone of spam filters, medical diagnosis tools, and language models.
Compiler data flow: live-variable analysis, reaching definitions, and constant propagation all propagate information along a control-flow graph. When loops are absent or abstracted away, the graph is a DAG and the analysis is a single topological sweep.
Coin change and knapsack on ordered items: many DP problems on sequences — coin change, knapsack — are secretly topological DP on an implicit DAG of states.

Whenever you see a table filled row by row, a pipeline processed stage by stage, or a scheduler that respects prerequisites, you are almost certainly looking at topological DP.

Conclusion

The lesson of DP on DAGs is not a clever trick — it is a principle: structure eliminates search. The moment you recognize that your problem's dependencies form a DAG, you know that a topological ordering exists, that optimal substructure holds trivially, and that a single $O(V + E)$ sweep will find the answer.

That is why topological DP quietly powers build tools, project schedulers, compilers, and probabilistic models. The hard problems — longest path on arbitrary graphs, optimal schedules with arbitrary dependencies — are NP-hard. But on a DAG, the same question becomes a clean linear scan.

The next time you fill in a DP table row by row, pause and ask: what is the DAG behind this table? The answer will almost always be there, and with it, the guarantee that no more than one pass is ever needed. See also how shortest paths generalize this idea to graphs with cycles, where topological order is no longer available.

Comments

Loading comments...

https://www.kipuhub.com/en/article/topological-dp/Content licensed under CC BY-NC 4.0.

Cookies & privacy

How topological order turns graph problems into a single sweep