What is Dynamic Programming on Graphs?
Learn how DP on graphs works with topological order, DAG shortest/longest path, and how to answer this DSA interview question.
Expected Interview Answer
Dynamic programming on graphs solves problems like shortest paths, longest paths, and counting paths by defining a DP state per node (or per node-and-extra-dimension) and computing it from already-solved neighboring states, which only works directly on graphs without cycles unless the cycles are handled explicitly.
On a directed acyclic graph (DAG), a topological order gives a safe processing sequence: by the time a node is processed, every node with an edge into it has already been finalized, so its DP value can be computed as a combination over incoming edges. Classic examples are longest path in a DAG, counting the number of distinct paths between two nodes, and DAG shortest path in O(V + E) without needing Dijkstra’s heap. When the graph has cycles — like a general weighted graph — plain topological DP breaks down, which is why Bellman-Ford instead relaxes edges repeatedly (V-1 rounds) and Dijkstra maintains a priority queue rather than a fixed processing order. Some problems restore acyclic structure by adding a dimension, such as “shortest path using at most k edges,” turning a cyclic graph problem into a DAG problem over (node, k) states.
- DAG DP runs in O(V + E), faster than general shortest-path algorithms
- Topological order guarantees dependencies are resolved first
- Extra state dimensions can restore acyclic structure to cyclic problems
- Unifies path counting, longest/shortest path, and scheduling problems under one technique
AI Mentor Explanation
A tournament committee scheduling a knockout-style progression, where some matches must finish before later matches can be scheduled, models this as a DAG of matches and computes the best possible cumulative highlight score reaching each match only after every prerequisite match’s score is finalized. Processing matches in bracket order — never scheduling a later match before its feeders are decided — is exactly a topological order, and each match’s best score is a DP combination over its incoming feeder matches. If rain delays created a scheduling loop where two matches depended on each other, this DAG approach would break, requiring a different technique like repeated relaxation instead. This is why DP on a match dependency graph only works cleanly when there is no cyclic scheduling dependency.
Step-by-Step Explanation
Step 1
Confirm or restore acyclic structure
Check the graph is a DAG; if not, add a state dimension (e.g. edges used) or use Bellman-Ford/Dijkstra instead.
Step 2
Topologically sort the nodes
Compute an order where every edge points from an earlier node to a later one, via DFS finish order or Kahn’s algorithm.
Step 3
Define the DP recurrence
Express each node’s value as a combination (min, max, sum, or count) over its incoming edges’ source-node values.
Step 4
Fill values in topological order
Process nodes in that order so every incoming value is already finalized, achieving O(V + E) total time.
What Interviewer Expects
- Explain why a topological order is required before DP can run
- Distinguish DAG DP (O(V + E)) from Dijkstra and Bellman-Ford for graphs with cycles
- Give at least one canonical example: longest path in a DAG, or counting distinct paths
- Describe how adding a state dimension can restore acyclic structure for problems like “shortest path with at most k edges”
Common Mistakes
- Attempting topological DP directly on a graph that has cycles
- Confusing DAG longest-path DP with Dijkstra, which only finds shortest paths and assumes non-negative weights
- Forgetting that DAG DP for longest path requires negating weights or flipping comparisons, not reusing shortest-path code unmodified
- Not recognizing when an extra dimension (like “edges used so far”) is needed to make an otherwise cyclic problem acyclic
Best Answer (HR Friendly)
“Dynamic programming on graphs means computing a value at each node using values already computed at the nodes that feed into it, which works cleanly when the graph has no cycles. I process nodes in topological order so every dependency is ready before I need it, and for graphs that do have cycles I switch to algorithms like Dijkstra or Bellman-Ford instead.”
Code Example
from collections import deque
def longest_path_dag(n, edges):
graph = {i: [] for i in range(n)}
indegree = [0] * n
for u, v, w in edges:
graph[u].append((v, w))
indegree[v] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for v, _ in graph[node]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
dist = [float("-inf")] * n
dist[order[0]] = 0
for u in order:
if dist[u] == float("-inf"):
continue
for v, w in graph[u]:
dist[v] = max(dist[v], dist[u] + w)
return distFollow-up Questions
- How would you count the number of distinct paths between two nodes in a DAG?
- Why does DAG longest-path DP not work directly if the graph has cycles?
- How would you find the shortest path using at most k edges in a graph with cycles?
- How does Bellman-Ford’s edge relaxation differ from topological DP on a DAG?
MCQ Practice
1. What ordering must nodes be processed in for DP on a DAG to be correct?
Topological order guarantees every node with an edge into a given node is processed before that node.
2. What is the time complexity of longest-path DP on a DAG with V vertices and E edges?
A topological sort plus one pass relaxing each edge once gives O(V + E) total time.
3. Why can topological DP not be applied directly to a graph with a cycle?
A topological order requires the graph to be acyclic; a cycle means no node in the cycle can be safely processed before the others.
Flash Cards
What must be true of a graph for direct topological DP to apply? — It must be a DAG (directed acyclic graph) — no cycles.
What is the time complexity of DAG longest-path DP? — O(V + E), using one topological sort plus one edge relaxation pass.
How can a cyclic shortest-path problem be made acyclic for DP? — Add an extra state dimension, e.g. (node, edges used so far), turning it into a DAG over that expanded state space.
Name two algorithms used instead of topological DP when a graph has cycles. — Dijkstra’s algorithm (non-negative weights) and Bellman-Ford (handles negative weights, detects negative cycles).