Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random
I am not 100% sure this answer is correct, but here goes:
I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink.
Given a graph $G$

Make a new empty digraph, $H$.
First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$.
Let $d(s,v)$ be the minimum distance from $s-v$; which we know from the BFS step of Dijkstra's shortest-path algorithm.
Then do the next step of Dijkstra's shortest-path algorithm, obtain the shortest-path, store it in $\mathbf p$ (by going backwards from $t$ to $s$).
Now start the following loop; expanation in comments, and below:

$q_0=\{t\}$
While $q_0 \ne \emptyset$

$q_1= \emptyset$
For $u \in q_0$

So we want to find all possible next nodes for this shortest-subpath from $t-u$
For all $\text{edge}(u,v) \in G$ such that $d(s,v) &lt; d(s,u)$

$v$ is a neighboring node, with less $d(s,\cdot)$ (it will be $1$ less)
Therefore, $t-u-v$ is possible subpath in a shortest path.
Put $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
Now we need to check $v$'s lesser-neighbors next turn.
Put $v \rightarrow q_1$




Set $q_0$ to $q_1$:

$q_0 \leftarrow q_1$







Essentially, I am collecting all possible nodes that can be used in the shortest-path, and placing them in $H$.
More on how this works:

Dijkstra's shortest-path algorithm works by first running a BFS, and marking all the nodes $v\in G$ with their-shortest paths from $s-v$. The next step is to go back from $t-s$, and follow the least-neighboring nodes back.
The thing is, here you can choose any of the least neighboring nodes. What I do here is collect all the least-neighboring nodes each step, which means I account for all the shortest-paths.
Now you quickly think, but hey, why is enumerating them exponential, but my way is not?
The answer is, because I use a set to avoid adding the same nodes twice, I avoid recalculating this for each possible path.

Now we have a DAG that we can traverse in any way from $t-s$, and obtain a shortest-reversed-path from $s-t$. The graph should have $t$ as the only source, and $s$ as the only sink.

If the above is correct, then I think we can take this a step further and solve the problem as follows.
Give each node in the DAG a node-weight; the node-weight will be the number of paths from from that node to $s$. Let us call this $w(v)$.
You can compute these quickly, see Algorithm that finds the number of simple paths from s to t in G.
Once we have the node-weight, we can uniformly pick a path by:

Layout the DAG as a level-structure (for visualization)
At each level, choose an arbitrary ordering between the nodes ie. a notion of &quot;left to right&quot;.
Traversing down the DAG: at each step $i$, $i \in \left[1,\left|\mathbf p\right|\right]$ (where $|\cdot|$ means size-of, in this case, the length of the shortest-path):

Let $u_i$ be the current node (starting at $t$)
Add up all the weights of the children of $u_i$, and using an RNG, choose one child node, $v_i$, uniformly between the weighted children.
Set $u_{i+1} = v_i$, and go to the next step