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

Question

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.

Answer 1

If you keep moving from node to node like that, you will end up visiting a node that was visited before. That's the point when you've entered a cycle, and the task becomes trivial.

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).