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.