DP on Graphs with Cycles (Bellman–Ford & Layers)

When the implicit graph has cycles, you cannot topo-DP blindly—use shortest path algorithms (Bellman–Ford) or add extra dimensions (number of edges used) to break cycles.

Why this shows up in the real world

Currency arbitrage detection (negative cycle). Game graphs with revisits.

Core idea (explained for students)

Either reformulate as shortest paths with SPFA/Bellman–Ford or expand state to include visit counts with a cap.

Try this in Python

def bellman_ford(n: int, edges: list[tuple[int, int, int]], src: int = 0) -> list[float]:
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist


print(bellman_ford(3, [(0, 1, 1), (1, 2, 1), (0, 2, 5)]))

Common mistakes

• Infinite relaxation loops without cycle checks.
• Storing naive dp[node] on cyclic graphs without policy.

Key takeaways

• Separate acyclic layers (DAG of SCCs) when using condensation graph.