Last update: June 8, 2022  Translated From: e-maxx.ru

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=\underset{k\text{ times}}{\underbrace{G\cdot G\cdots G}}=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   $\mathrm{\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   $\mathrm{\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]=\underset{p=1\dots n}{min}(L_k[i][p]+G[p][j])$$ 

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⟺C_{ij}=\underset{p=1\dots n}{min}(A_{ip}+B_{pj})$$ 

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

  $$L_k=\underset{k\text{times}}{\underbrace{G\odot \dots \odot G}}=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^{\prime }$  and add the edge   $(v,v^{\prime })$  and the loop   $(v^{\prime },v^{\prime })$ . 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^{\prime }$  with exactly   $k+1$  edges, since there is a bijection that maps every path   $[p_0=i,p_1,\dots ,p_{m-1},p_m=j]$  of length   $m\le k$  to the path   $[p_0=i,p_1,\dots ,p_{m-1},p_m=j,j^{\prime },\dots ,j^{\prime }]$  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$ .

Contributors:
• jakobkogler (92.47%)
• adamant-pwn (6.45%)
• wikku (1.08%)