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](https://i.stack.imgur.com/fhxz1.png)


$$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.



Solution to the sum of k-step path lengths between node pairs in directed weighted graphs
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](https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication)


