Algorithms 01: Dynamic Programming on Graphs

This article systemizes the core nature of Dynamic Programming when applied to graph structures. I present it in clear sections to help readers grasp the key focus and approach — especially suitable for beginners or those looking to review the concept.

1. Core Idea

In classical DP problems (e.g., Fibonacci, Knapsack), states usually have a natural order from 1 to n. On graphs, the dependency relationships between nodes do not have a fixed order; therefore, it is necessary to determine an appropriate computation order to ensure that dependencies are satisfied before computing the value of a node.

Topological order is the ordering of vertices in a directed graph such that if a directed edge u → v exists, u appears before v. If the graph is a DAG (Directed Acyclic Graph), we can perform a topological sort and safely use this order for DP. If the graph contains cycles, topological sort is not applicable; in that case, alternative techniques such as DFS combined with memoization or iterative relaxation algorithms like Bellman–Ford / Floyd–Warshall are used until the values converge.

Illustrative example: to compute the value of node 4 (assuming the value is the total path from 1 to 4), we first need the results of nodes 2 and 3; to have 2 and 3, we must have the result of 1. Therefore, it is necessary to arrange the order so that each node is computed after the nodes it depends on.

ex: topo = [1, 2, 3, 4]

dp[1] = base
dp[2] = f(dp[1])
dp[3] = f(dp[1])
dp[4] = f(dp[2], dp[3])

Thus, the computation order always ensures that dependencies already have values.

2. Example: Longest Path on DAG

Problem: Given n vertices and a set of edges, find the length of the longest path on a DAG. Idea: Traverse the vertices in topological order and update the values for adjacent vertices.

For each edge u → v, perform:

dp[v] = max(dp[v], dp[u] + 1)

Pseudo code:

topo = topological_sort(graph)
dp = [0 for _ in range(n)]
for u in topo:
    for v in graph[u]:
        dp[v] = max(dp[v], dp[u] + 1)
return max(dp)

Time complexity: O(V + E) if a topological order is already available. Topo ensures that a vertex is never updated before its prerequisites have been processed.

3. When Graphs Have Cycles

If the graph contains cycles, topological sort is not applicable. Common alternatives include:

DFS + memoization: use DFS to compute values on demand, storing results (memo) to avoid recomputation. For problems requiring the longest path on a graph with cycles, cycles must be handled appropriately (e.g., detecting infinity or cutting cycles according to the problem requirements).
Bellman–Ford / Floyd–Warshall: iterative algorithms that relax edges multiple times until the values converge (or detect the existence of a negative cycle with Bellman–Ford).

DFS + memo pseudo code:

def dfs(u):
    if seen[u]:
        return dp[u]
    seen[u] = True
    dp[u] = 1 + max(dfs(v) for v in graph[u])
    return dp[u]

Bellman–Ford: iterate through all edges V-1 times, each time performing an update of the form dist[v] = min(dist[v], dist[u] + w). In essence, this is a form of iterative DP (iterative relaxation) until the values stabilize.

4. Real-World Analogy

Real-world dependency management problems accurately reflect the thinking of DP on graphs:

Airflow DAG: a task only runs when the tasks it depends on have completed.
Compiler dependency graph: module A must be compiled before module B if B depends on A.
Neural network forward pass: traverse the computation graph in topological order to compute the values of the nodes.

Ultimately, these are all dependency resolution.

5. Key Takeaways

On a DAG, prefer using topo DP with a complexity of O(V + E).
If the graph contains cycles, consider using DFS + memoization or iterative relaxation algorithms like Bellman–Ford.
The focus is not on formulas; it is on managing information flow (dependencies) and computation order.
DP on graphs = reuse + ordering + dependency control.

6. Related LeetCode Problems

For practice, you can refer to the following problems (from easy to medium-hard):

207. Course Schedule — cycle detection + topo sort
210. Course Schedule II — construct topo order
329. Longest Increasing Path in a Matrix — DP on an implicit graph in a grid
1514. Path with Maximum Probability — DP combined with Dijkstra
787. Cheapest Flights Within K Stops — a variant of Bellman–Ford

7. Personal Reflection

I used to understand DP as a rigid set of state transition formulas. After diving deeper, I realized that the essence of DP is managing information flow within a dependency network. Graphs only make the concept more abstract, but the principle remains the same: solve the simple parts first, store the results, and then use them to compute the more complex parts.

Once you grasp this principle, algorithms like Bellman–Ford, Floyd–Warshall, or topo DP become much more intuitive. A useful habit: draw the dependency graph before coding and experiment with a small example (4–5 vertices) to observe the order and how values propagate.

Practical Principles:

Understand the computation flow (simulate flow) before implementing code — Understand > Memorize.
DP = reuse + ordering + dependency management — from there, you can reconstruct the algorithm without having to memorize formulas.
If there are cycles, do not force a topo sort; switch to an iterative update method like Bellman–Ford and continue to relax until stable.
Always clearly identify 'who depends on whom' — visualization helps to quickly grasp dependencies.
Start from the base case; think forward (past → future) or backward (goal → start) depending on the problem.
If you find yourself computing the same value repeatedly — use memoization; double-check boundaries and base cases to avoid common errors.

Ghi chú: Đây là chia sẻ từ góc nhìn người bắt đầu nhằm giúp người học hệ thống lại kiến thức. Việc thực hành và giải nhiều bài sẽ giúp nâng cấp khả năng làm chủ các biến thể nâng cao hơn.

Seatek lab