# Graph traversal of n steps

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`?

-
Can you use an edge more than once in one path? – gabitzish Apr 27 '12 at 6:57
Yes. (Walrus filler) – skinkelynet Apr 27 '12 at 6:58
Then there's an infinite number of paths? – aib Apr 27 '12 at 7:01
@aib: since the length of the paths is finite, there is only a huge number of combinations in some cases :) – Matthieu M. Apr 27 '12 at 8:45
Ah, of `n` steps. Missed that. – aib Apr 27 '12 at 11:56

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.

-
Can you add details on why it works? – Antoine Apr 27 '12 at 7:06
Yes of course, no problem. Starting to work on that. – Boris Strandjev Apr 27 '12 at 7:07
@Antoine Done - I added proof by induction, hopefully it will be understandable enough. – Boris Strandjev Apr 27 '12 at 7:21
Thanks you for the great answer. – Antoine Apr 27 '12 at 7:22
What is `n` in the sum? – huon Apr 27 '12 at 7:29

It's quite like a dynamic programming problem:

1. define a f[n][m] to be the number of paths from the starting point to point n in m steps
2. from every point n to its adjacent k, you have formula: f[k][m+1] = f[k][m+1] + f[n][m]
3. in the initialization, all f[n][m] will be 0, but f[starting_point][0] = 1
4. 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) {
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}