# Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of seemingly unnecessary random bits.

My question is:

Can the solution be improved to use a single random number in interval $[0,w(t))$, where $w(t)$ is the total number of shortest paths from $s\text{-}t$.

Alternatively, can the solution be improved to use $\left\lceil \log_2 w(t)\right\rceil$ 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.