How many paths of length K are there between A and B? (2021)

Summary

How Many Paths of Length K are There Between A and B? : And I Show You How Deep the Rabbit Hole Goes... Here's a (surprisingly interesting) programming problem: Given a directed unweighted graph with V vertices and E edges, how many paths of length K are there from node A to node B? Paths may visit the same node or edge multiple times. To avoid dealing with very large numbers, assume that we're computing our answer modulo a large prime. Figure There are 2 paths of length 2 from node A to node B cluster_first Graph cluster_second Path 1 cluster_third Path 2 A1 A C1 A1->C1 D1 A1->D1 B1 B C1->B1 D1->B1 A2 A C2 A2->C2 D2 A2->D2 B2 B C2->B2 D2->B2 A3 A C3 A3->C3 D3 A3->D3 B3 B C3->B3 D3->B3 This problem is fairly standard - many of you may have seen it or heard it in an interview. Personally, I've seen this problem on Hackernews in some form at least three times, here, here, and here. I found this comment from the last link particularly interesting. He states of the most advanced level: I've never seen anyone get this and I only learned about it after months of asking this question. And that's where he left the problem. Seems like a pretty cool problem with plenty of depth, doesn't it? As it turns out, this problem has even more depth than that Google interviewer thought. What if I told you, that drawing on concepts from coding theory, abstract algebra, and signal processing, we could solve this problem in O(EV+Vlog⁡Vlog⁡K)O(EV + V \log V \log K)O(EV+VlogVlogK) time? To my knowledge, despite being a common problem, I have not seen this faster solution presented anywhere. Let's dive down the rabbit hole of solutions to this problem, starting from the top. The most straightforward solution to this problem is to enumerate all the paths and stopping once our path reaches K nodes. We can implement it with a breadth first search, like so: ans = 0 queue = [(A, 0)] while not queue.empty(): curNode, curLength = queue.front() queue.pop() if curLength == K: if curNode == B: ans += ...