Graph Theory37 sections · 1633 units
Open in Course

Combining Two DPs

Paths through a node

You can combine forward DP (from source) and backward DP (to destination) to count paths that pass through a specific node. Compute forward[u] = paths from source to uu, and backward[u] = paths from uu to destination.

The number of paths through node uu is forward[u] * backward[u]. Sum over all nodes to count total paths, or find the node that maximizes forward[u] * backward[u] to find the most popular intermediate node.