Solution to the sum of k-step path lengths between node pairs in directed weighted graphs

Question

In a non weighted graph, the adjacency matrix ($A$) raised to the power $k$ will return the number of k-step paths between nodes $i$ and $j$ at the entry $a_{ij}$. Is there an equivalent for weighted graphs? I.e. to obtain the sum of the cumulative weights of all paths between node pairs?

Applying the same approach as above, but to a weighted adjacency matrix, i.e. raising to the power $k$, returns the sum of the product of the weights along each $k$ step path between node pairs. This is useful when edge weight represents some probability (e.g. Markov models), however not when edge weight represents a length (e.g. geospatial network).

Note I want to avoid path search algorithms (e.g. Dijkstra's or Yen's) if possible, as this will be applied to very large networks so efficiency is important.

Example: Given a 4-node digraph (image linked below), with the weighted adjacency matrix (infinity represents no connection between nodes):

Digraph described in the example

$$A = \begin{matrix} \infty & 2 & 3 & \infty \\ 2 & \infty & 5 & 1 \\ \infty & \infty & \infty & 7 \\ \infty & 1 & \infty & \infty \\ \end{matrix} $$

where e.g. the connection between nodes B & C is of length 5. I want to find the n-step length matrix, which for the 2 step case would be:

$$A_2 = \begin{matrix} 4 &\infty & 7 & 13 \\ \infty & 6 & 5 & 12 \\ \infty & 8 & \infty & \infty \\ 3 & \infty & 6 & 2 \\ \end{matrix} $$

Thanks in advance for any help.

Answer 1

Let $A^k_{i,j} = (n^k_{i,j}, s^k_{i,j})$ where $n^k_{i,j}$ is the number of paths of length $k$ between $i$ and $j$, and $s^k_{i,j}$ is the sum of the lengths between these paths.
$A^1_{i,j} = (1, w_{i,j})$ if $ij$ is an edge, else $A^1_{i,j}=(0,0)$
The idea of the recurrence is that a $(k+k')$-step path from $i$ to $j$ is composed of a $k$-step path from $i$ to an intermediate vertex $c$ followed by a $k'$-step path from $c$ to $j$.
Let fix $c$. Let $n_1$ (resp $n_2$) be the number of $k$-step paths from $i$ to $c$ (resp. $k'$-step paths from $c$ to $j$) and $s_1$ (resp. $s_2$) the sum of weigths on these paths. We can easily see that the number of $(k+k')$-step paths from $i$ to $j$ passing through $c$ at step $k$ is $n_1n_2$. The sum of weights is $s_1n_2 + s_2n_1$ because each path from $i$ to $c$ will appear in exactly $n_2$ paths, and conversely. To get the total number of $(k+k')$-step paths from $i$ to $j$, we just need to sum over the $c$. So the recurrence is given by :
$$A^{k+k'}_{i,j} = (n^{k+k'}_{i,j}, s^{k+k'}_{i,j}) = \sum_{c\in V}(n^k_{i,c}n^{k'}_{c,j}, n^k_{i,c}s^{k'}_{c,j}+s^k_{i,c}n^{k'}_{c,j})$$

We can adapt the definition of the matrix multiplication by replacing the multiplication by : $(n_1,s_1)\otimes(n_2,s_2) = (n_1n_2, n_1s_2 + n_2s_1)$
and addition by :
$(n_1,s_1)\oplus(n_2,s_2) = (n_1+n_2, s_1+s_2)$
With it, we have :
$$A^{k+k'}_{i,j} = \bigoplus_{c\in V} A^{k}_{i,c}\otimes A^{k'}_{c,j}$$ and so $A^kA^{k'} = A^{k+k'}$

The new matrix multiplication is associative, so matrix exponentiation by squaring still work.

---

This kind of redefinition of the matrix multiplication is common when dealing with shortest paths, see the min-plus matrix multiplication