# In a directed graph, efficiently determine node reached after traveling k edges from the starting node

I am trying to solve a problem where I am given a directed graph with $$n$$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $$1$$ to $$n$$. Starting at node $$1$$, the problem consists in writing an algorithm which determines on which node we end up after moving along $$k$$ edges.

Here is an example graph:

If $$k=2$$, then the final node will be $$3$$. If $$k=9$$, then we will reach node $$5$$ instead.

In order to solve this problem, I chose to represent the graph as a one-dimensional array, where the index of the array represents the current node and the value at said index the node which we can reach. Since in Python, arrays are 0-indexed, the first value is 0.

The following array represents the graph above:

# indexes:  0  1  2  3  4  5
my_graph = [0, 2, 3, 5, 1, 3]


From here on, I utilized a naive approach to determine the final node:

current_node = 1

while k > 0:
k -= 1
current_node = my_graph[current_node]

print(current_node)


This code works fine and outputs the correct answer, however it is obviously too slow for huge values of $$k$$ (upwards of $$10^{15}$$). I am guessing that dynamic programming could be of help in order to produce faster results, but I am having a hard time determining the "smallest subproblem" here...

I would appreciate any help or hints towards an efficient algorithm which solves the described problem.

Since the question was tagged with dynamic-programming, you may be interested in this alternative approach. To simplify things, let's assume that $$k$$ is a power of $$2$$, which means that $$k = 2^p$$ for some $$p \ge 0$$. To reach the $$2^p$$-th node from the initial node $$U$$, you can first move by $$2^{p-1}$$ edges to reach node $$V$$, and then from $$V$$, you can go along another $$2^{p-1}$$ edges to reach the destination.
Here are the subproblems you need: for each node $$u$$, denote $$dp(u, p)$$ as the node you reach after moving along $$2^p$$ edges. You may want to derive the formula for this yourself. To tackle the problem for the general case of any $$k$$, you can partition $$k$$ into powers of $$2$$, and move along each power of $$2$$ one by one.
For instance, if $$k = 13$$, then
$$k = 13 = 2^3 + 2^2 + 2^0$$
The number of powers of $$2$$ in the partition of $$k$$ is at most $$\lfloor \log_2 k \rfloor$$, hence the complexity is $$O(\log k)$$ (excluding the cost of calculating the dp table).