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.
Best Answer
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