Graph Theory37 sections · 1633 units
Open in Course

Multiple Destinations

Sum over all endpoints

What if you want to count paths from a single source to any of several destinations?

Run the DP once, then sum dp[u] for all destination nodes. For example, if destinations are nodes 77, 88, and 99, the answer is dp[7] + dp[8] + dp[9]. Each destination's count is independent. This works because paths to different destinations do not interfere with each other. You are adding up separate counts.