To sample the shortest paths according to \(\pi _{G}\) , RK first chooses
a node pair \((s,t)\)  uniformly at random and performs an SSSP search from \(s\) , keeping also track of the number \(\sigma _{sv}\) 
of shortest paths from \(s\)  to \(v\)  and of the list of predecessors
\(P_{s}(v)\)  for any node \(v\) . Then one shortest path is selected:
Starting from \(t\) , a predecessor \(z\in P_{s}(t)\) 
is selected with probability \(\sigma _{sz}/\sum _{w\in P_{s}(t)}\sigma _{sw}=\sigma _{sz}/\sigma _{st}\) .
The sampling is repeated iteratively
until node \(s\)  is reached. Algorithm  in the Appendix is the
pseudocode for RK. Function computeExtendedSSSP is
an SSSP algorithm that keeps track of the number of shortest paths and
of the list of predecessors while computing distances, as in BA [1]}.
