Graph traversal of n steps

Question

Given a simple undirected graph like this: Starting in D, A, B or C (`V_start`)—I have to calculate how many possible paths there are from the starting point (`V_start`) to the starting point (`V_start`) of `n` steps, where each edge and vertex can be visited an unlimited amount of times. I was thinking of doing a depth first search, stopping when `steps > n || (steps == n && vertex != V_start)`, however, this becomes rather expensive if, for instance, `n = 1000000`. My next thought led me to combining DFS with dynamic programming, however, this is where I'm stuck. (This is not homework, just me getting stuck playing around with graphs and algorithms for the sake of learning.) How would I go about solving this in a reasonable time with a large `n`?

Accepted Answer

This task is solved by matrix multiplication.

Create matrix `n`x`n` containing 0s and 1s (1 for a cell `mat[i][j]` if there is path from `i` to `j`). Multiply this matrix by itself `k` times (consider using fast matrix exponentiation). Then in the matrix's cell `mat[i][j]` you have the number of paths with length `k` starting from `i` and ending in `j`.

NOTE: The fast matrix exponentiation is basically the same as the fast exponentiation, just that instead you multiply numbers you multiply matrices.

NOTE2: Lets assume `n` is the number of vertices in the graph. Then the algorithm I propose here runs in time complexity O(log k * n3) and has memory complexity of O(n 2). You can improve it a bit more if you use optimized matrix multiplication as described here. Then the time complexity will become O(log k * nlog27).

EDIT As requested by Antoine I include an explanation why this algorithm actually works:

I will prove the algorithm by induction. The base of the induction is obvious: initially I have in the matrix the number of paths of length 1.

Let us assume that until the power of `k` if I raise the matrix to the power of `k` I have in `mat[i][j]` the number of paths with length `k` between `i` and `j`.

Now lets consider the next step `k + 1`. It is obvious that every path of length `k + 1` consists of prefix of length `k` and one more edge. This basically means that the paths of length `k + 1` can be calculated by (here I denote by `mat_pow_k` the matrix raised to the `k`th power)

num_paths(x, y, k + 1) = sumi=0i<n mat_pow_k[x][i] * mat[i][y]

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

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

Graph traversal of n steps

Solution

Problem