Max Propagation and Relaxation-Style DP

Relaxation style: propagate best values along edges or layers until stable—like shortest paths or DP on implicit graphs with monotone updates.

Why this shows up in the real world

Spreadsheet recalc orders cell dependencies. Relaxation labeling in vision.

Core idea (explained for students)

Repeatedly dp[v]=max(dp[v], f(dp[u])) until no change or for fixed iterations equal to longest path length.

Try this in Python

def relax_edges(n: int, edges: list[tuple[int, int, int]]) -> list[int]:
    dist = [-(10**18)] * n
    dist[0] = 0
    for _ in range(n - 1):
        ch = False
        for u, v, w in edges:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                ch = True
        if not ch:
            break
    return dist


print(relax_edges(3, [(0, 1, 2), (1, 2, 3), (0, 2, 1)]))

Common mistakes

• Non-convergence when cycles without proper formulation.
• Doing too many redundant passes—use topo when acyclic.

Key takeaways

• Count passes and stop early when dp unchanged.