Schedule of n steps

Question

Given a simple undirected graph as follows:

Starting from D, A, B or C ( V_start ) - I need to calculate how many possible paths from the starting point ( V_start ) to the starting point ( V_start ) are n steps, where each edge and vertex can be visited an unlimited number of times.

I was thinking about the first depth search, stopping at steps > n || (steps == n && vertex != V_start) steps > n || (steps == n && vertex != V_start) , however this becomes quite expensive if, for example, n = 1000000 . My next thought led me to combine DFS with dynamic programming, but this is where I got stuck.

(This is not homework, I just got stuck playing with graphs and algorithms for the sake of learning.)

How can I solve this in a reasonable amount of time using large n ?

Answer 1

This problem is solved by multiplying the matrix.

Create an n x n matrix containing 0s and 1s (1 for the cell mat[i][j] if there is a path from i to j ). Multiply this matrix by yourself k times (consider the possibility of a quick exponent of the matrix). Then in the matrix cell mat[i][j] you have the number of paths with length k , starting from i and ending with j .

NOTE Quick exponentiation of a fast matrix is ​​basically the same as quick exponentiation, just instead you multiply numbers by matrix multiplication.

NOTE2: Assume that n is the number of vertices in the graph. Then the algorithm proposed here is executed in the time complexity O (log _k * n ³ ) and has the memory complexity O (n ² ). You can improve it a bit more if you use optimized matrix multiplication, as described here . Then O (log _k * n ^{log ₂ 7} ) becomes the time complexity.

---

EDIT According to Antoine’s request, I’ll explain the explanation of why this algorithm really works:

I will prove the algorithm by induction. The basis of induction is obvious: initially in my matrix there are a number of paths of length 1.

Suppose that to level k , if I raise the matrix to degree k , I have in mat[i][j] number of paths with length k between i and j .

Now consider the next step k + 1 . Obviously, each path of length k + 1 consists of a prefix of length k and one more edge. This basically means that paths of length k + 1 can be calculated (here I denote by mat_pow_k matrix raised to the k degree)

num_paths (x, y, k + 1) = sum _{i = 0} ^{i <n} mat_pow_k [x] [i] * mat [i] [y]

Again: n is the number of vertices in the graph. This may take some time to understand, but basically the original matrix has 1 in its cell mat[i][y] only if there is a direct border between x and y . And we count all the possible prefixes of such an edge to form a path of length k + 1 .

However, the last thing I wrote actually calculates the k + 1 st power of mat , which proves the step of induction and my statement.

Answer 2

This is very similar to a dynamic programming problem:

• define f [n] [m] as the number of paths from the starting point to point n in steps m
• from each point n to neighboring k, you have the formula: f [k] [m + 1] = f [k] [m + 1] + f [n] [m]
• in initialization, all f [n] [m] will be 0, but f [start_point] [0] = 1
• so you can calculate the final result

pseudo code:

 memset(f, 0, sizeof(f)); f[starting_point][0] = 1; for (int step = 0; step < n; ++step) { for (int point = 0; point < point_num; ++point) { for (int next_point = 0; next_point < point_num; ++ next_point) { if (adjacent[point][next_point]) { f[next_point][step+1] += f[point][step]; } } } } return f[starting_point][n]