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