[Solved]: Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

1. Make a new empty digraph, $H$.
2. First: run the BFS part of Dijkstra’s shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$.
3. Let $d(s,v)$ be the minimum distance from $s-v$; which we know from the BFS step of Dijkstra’s shortest-path algorithm.
4. 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$).
5. 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) < 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 $vin 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 “left to right”.
• Traversing down the DAG: at each step $i$, $i in left[1,left|mathbf pright|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