# Number of paths of fixed length / Shortest paths of fixed length

The following article describes solutions to these two problems built on the same idea: reduce the problem to the construction of matrix and compute the solution with the usual matrix multiplication or with a modified multiplication.

## Number of paths of a fixed length

We are given a directed, unweighted graph $$G$$ with $$n$$ vertices and we are given an integer $$k$$. The task is the following: for each pair of vertices $$(i, j)$$ we have to find the number of paths of length $$k$$ between these vertices. Paths don't have to be simple, i.e. vertices and edges can be visited any number of times in a single path.

We assume that the graph is specified with an adjacency matrix, i.e. the matrix $$G[][]$$ of size $$n \times n$$, where each element $$G[i][j]$$ equal to $$1$$ if the vertex $$i$$ is connected with $$j$$ by an edge, and $$0$$ is they are not connected by an edge. The following algorithm works also in the case of multiple edges: if some pair of vertices $$(i, j)$$ is connected with $$m$$ edges, then we can record this in the adjacency matrix by setting $$G[i][j] = m$$. Also the algorithm works if the graph contains loops (a loop is an edge that connect a vertex with itself).

It is obvious that the constructed adjacency matrix if the answer to the problem for the case $$k = 1$$. It contains the number of paths of length $$1$$ between each pair of vertices.

We will build the solution iteratively: Let's assume we know the answer for some $$k$$. Here we describe a method how we can construct the answer for $$k + 1$$. Denote by $$C_k$$ the matrix for the case $$k$$, and by $$C_{k+1}$$ the matrix we want to construct. With the following formula we can compute every entry of $$C_{k+1}$$:

$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$

It is easy to see that the formula computes nothing other than the product of the matrices $$C_k$$ and $$G$$:

$C_{k+1} = C_k \cdot G$

Thus the solution of the problem can be represented as follows:

$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k$

It remains to note that the matrix products can be raised to a high power efficiently using Binary exponentiation. This gives a solution with $$O(n^3 \log k)$$ complexity.

## Shortest paths of a fixed length

We are given a directed weighted graph $$G$$ with $$n$$ vertices and an integer $$k$$. For each pair of vertices $$(i, j)$$ we have to find the length of the shortest path between $$i$$ and $$j$$ that consists of exactly $$k$$ edges.

We assume that the graph is specified by an adjacency matrix, i.e. via the matrix $$G[][]$$ of size $$n \times n$$ where each element $$G[i][j]$$ contains the length of the edges from the vertex $$i$$ to the vertex $$j$$. If there is no edge between two vertices, then the corresponding element of the matrix will be assigned to infinity $$\infty$$.

It is obvious that in this form the adjacency matrix is the answer to the problem for $$k = 1$$. It contains the lengths of shortest paths between each pair of vertices, or $$\infty$$ if a path consisting of one edge doesn't exist.

Again we can build the solution to the problem iteratively: Let's assume we know the answer for some $$k$$. We show how we can compute the answer for $$k+1$$. Let us denote $$L_k$$ the matrix for $$k$$ and $$L_{k+1}$$ the matrix we want to build. Then the following formula computes each entry of $$L_{k+1}$$:

$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$

When looking closer at this formula, we can draw an analogy with the matrix multiplication: in fact the matrix $$L_k$$ is multiplied by the matrix $$G$$, the only difference is that instead in the multiplication operation we take the minimum instead of the sum.

$L_{k+1} = L_k \odot G,$

where the operation $$\odot$$ is defined as follows:

$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$

Thus the solution of the task can be represented using the modified multiplication:

$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{times}} = G^{\odot k}$

It remains to note that we also can compute this exponentiation efficiently with Binary exponentiation, because the modified multiplication is obviously associative. So also this solution has $$O(n^3 \log k)$$ complexity.

## Generalization of the problems for paths with length up to $$k$$

The above solutions solve the problems for a fixed $$k$$. However the solutions can be adapted for solving problems for which the paths are allowed to contain no more than $$k$$ edges.

This can be done by slightly modifying the input graph.

We duplicate each vertex: for each vertex $$v$$ we create one more vertex $$v'$$ and add the edge $$(v, v')$$ and the loop $$(v', v')$$. The number of paths between $$i$$ and $$j$$ with at most $$k$$ edges is the same number as the number of paths between $$i$$ and $$j'$$ with exactly $$k + 1$$ edges, since there is a bijection that maps every path $$[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j]$$ of length $$m \le k$$ to the path $$[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j, j', \ldots, j']$$ of length $$k + 1$$.

The same trick can be applied to compute the shortest paths with at most $$k$$ edges. We again duplicate each vertex and add the two mentioned edges with weight $$0$$.