How many paths of length K are there between A and B? (2021)
17 days ago
- #dynamic-programming
- #graph-theory
- #linear-algebra
- The problem involves counting paths of length K from node A to node B in a directed unweighted graph, allowing revisits.
- Initial solutions include a BFS approach (exponential time) and a dynamic programming approach (O(K*E) time).
- Advanced solutions involve matrix exponentiation (O(V^3 log K) time) and leveraging linear recurrences.
- Cayley-Hamilton theorem is used to convert matrix exponentiation problems into linear recurrence problems.
- Berlekamp-Massey algorithm helps find the shortest linear recurrence from sequence terms, enabling faster computation.
- Polynomial arithmetic and annihilators are used to evaluate terms of linear recurrences efficiently.
- The final approach combines DP, Berlekamp-Massey, and polynomial techniques to solve the problem in O(V^2 log K) time.