The idea: a DP is a path through its subproblems

Every dynamic program has subproblems, and each one is solved from a few others. Draw each subproblem as a vertex and draw an edge u→v when v reads u. There can be no cycle, because a value cannot wait for itself. So the subproblems form a DAG (directed acyclic graph), and the DP's answer is the best path through it: the longest one for a max problem, the shortest one for a min problem. The order in which a table is filled is a topological order of that DAG: every vertex comes after all the vertices it reads.

Left: a 3 by 4 DP table filled row by row, cells numbered 1 to 12. Right: the same cells as vertices with an arrow from the cell above and from the cell to the left into every cell; the numbers are a topological order
A DP table is a DAG: each cell has an edge from every cell it reads, and the fill order is a topological order.

The recurrence

Let dist[v] be the length of the longest path that ends at v. The last edge of that path comes from some predecessor u, and the part before it must itself be a longest path to u. So:

dist[s] = 0                 (the start)
dist[v] = max over edges u→v of  dist[u] + w(u→v)
dist[v] = −∞                when no path reaches v

In the animation a vertex reads one box per edge coming in, the boxes fly to the reading row, and the vertex keeps the largest. On the sample DAG, A reads 0+5 from S and 3+4 from C, so dist[A] = 7. At the end dist[T] = 18 (Demo: sample DAG).

Why topological order

The rule only works if dist[u] is final when v reads it. In a topological order every edge points forward, so all of v's predecessors are done before v: one pass over the vertices, each in-edge read once. You get such an order with Kahn's algorithm (keep taking a vertex with no edge left coming in) or with depth-first search (reverse finishing order).

Take the vertices in another order and the pass can fail. By name, A comes before C, so A reads dist[C] = −∞ and settles for 5 instead of 7. Nothing goes back to fix A, and the error spreads: B, D, E and T are all too small, and T ends at 16 instead of 18 (Demo: wrong order).

Two rows. Topological order S C A: when A is computed, C is already 3, so A = max(0+5, 3+4) = 7, correct. Order by name A then C: when A is computed, C is still minus infinity, so A = max(0+5, minus infinity) = 5, wrong
Read a predecessor before it is final and the value is too small, with no second chance.

Which path? Follow the parent pointers

The pass gives numbers, not the path. So each vertex also keeps the in-edge that won, its parent pointer (blue in the animation). After the pass, start at T and follow the blue edges back: T ← E ← D ← A ← C ← S, so the longest path is S → C → A → D → E → T, of length 3 + 4 + 4 + 3 + 4 = 18. Greedy fails here: taking the heaviest edge out of each vertex goes S → A → D → E → T and gets only 16.

Longest or shortest: change max to min

Nothing else changes. With min the same pass finds the shortest path: S → A → B → T, 5 + 1 + 5 = 11 (Demo: min instead of max). Negative edge weights are fine too, because the order, not the weights, guarantees each value is final.

Cycles are what break it. In a graph with a cycle there is no topological order: some vertex would have to wait for itself. For shortest paths there are other algorithms. For the longest simple path on a general graph there is no fast algorithm known: the problem is NP-hard, since a path through all n vertices would be a Hamiltonian path. The DAG is what makes it easy.

GraphLongest pathShortest path
DAG (this page)O(V + E), one passO(V + E), one pass
General graphNP-hard (simple paths)Dijkstra, Bellman-Ford

A grid path sum is a longest path

Walk from the top-left cell to the bottom-right, moving right or down, and add the numbers. Every cell is a vertex with an edge from the cell above and the cell to its left, and the weight sits on the vertex. The rule best[cell] = value + max(best[up], best[left]) is the same recurrence, and filling the table row by row is the topological order. The best sum is 18 (Demo: grid), and with min it is the classic minimum path sum, 11. See Grid Paths for the table view.

LIS is a longest path

In the array 2 5 1 6 3 7 make each element a vertex and add an edge i→j when i < j and a[i] < a[j]. An increasing subsequence is then a path, and the longest one is the longest increasing subsequence. Each vertex counts 1 and a path may start anywhere, so L[j] = 1 + max(0, L[i] for every edge i→j). The animation finds L = 4 for 2 5 6 7 (Demo: LIS). Here there is no fixed end: the answer is the best L anywhere.

Time and space

The topological sort and the pass are both O(V + E): every vertex is processed once and every edge is read once, when its head is processed. The values and parent pointers take O(V). For a DP this is the usual "number of subproblems times the work per subproblem": LCS has n·m vertices with 3 edges each, LIS has n vertices and up to n²/2 edges. The same view explains memoization vs tabulation: memoization is a depth-first search of the DAG, and tabulation walks it in a topological order fixed in advance. DP on trees uses post-order, which is a topological order of the tree.

The same pass in push form, compared with Dijkstra and Bellman-Ford, is on shortest paths in a DAG.

What the page leaves out

Computing the topological order step by step (see the topological sort pages); detecting a cycle when Kahn's algorithm gets stuck; the push form of the same pass (relax each vertex's out-edges instead of reading its in-edges); the critical path method for project scheduling, which is this longest path with tasks as edges; counting paths in a DAG; and all-pairs versions.