1
$\begingroup$

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:

graph example 1

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.