Uniformly random efficient sampling of shortest s-t paths, with optimal random bits
D. W. computes for each node $v \in S$ the number of paths $n(v)$ from $v$ to $t$. Using this information, it is easy to decode a number in the range $[0,n(s))$ to a unique path from $s$ to $t$ in $S$ (and so in the original graph). More generally, at each node $v$ we will come up with a procedure to map $[0,n(v))$ to a unique path from $v$ to $t$. Let the children of $v$ be $v_1,\ldots,v_k$. The idea is to write
$$ [0,n(v)) = [0,n(v_1)) \cup [n(v_1),n(v_1)+n(v_2)) \cup \cdots [n(v_1)+\cdots + n(v_{k-1}), n(v_1)+\cdots+n(v_k)), $$
and use the $i$th component to encode paths going through $v_i$. By subtracting $n(v_1) + \cdots + n(v_{i-1})$, we then reduce the problem to decoding a number in $[0,n(v_i))$ to a unique path from $v_i$ to $t$. Pseudocode left to the reader.