Graph Theory37 sections · 1633 units
Open in Course

Multiple Sources

Initialize multiple base cases

Some problems have multiple starting points. For example, you might be able to start at any of several nodes and want to count paths to a single destination. Initialize dp[u] = 1 for all source nodes and dp[u] = 0 for all others.

Then run the standard DP. The counts from each source naturally combine. If you want paths from any source to any destination, you might need to run the DP once per source, or use a different approach like matrix exponentiation.