Consider a directed, weighted graph $G$. Let $s$ and $t$ be two distinct vertices of $G$ and consider a walker that starts at $s$ and traverses a random shortest path from $s$ to $t$, chosen uniformly at random from all shortest paths from $s$ to $t$.
Question: What is the transition matrix $P$ that characterises this "random walk" (specifically, choosing a random shortest path) that starts at $s$ and ends at $t$?
Intuitively, it seems clear that $P$ is given by \begin{equation} P_{ij} = \frac{\omega_{ij}}{\sum_k \omega_{ik}}\,, \end{equation} where $\omega_{ij}$ is the number of shortest paths from $s$ to $t$ that traverse the directed edge $(i,j)$.
To see this, consider the $k$ shortest paths from $s$ to $t$. If we let $k$ walkers walk each of the $k$ shortest paths, their empirical transition matrix is given by $P$.
However, this is not a rigorous proof. Can someone provide a rigorous proof or fill in the missing step(s)?
