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

Problem Detail: 

Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ and $t$? For simplicity, we can assume $G$ is simple, undirected and unweighted.

Even in many restricted graphs, the number of shortest paths between $s$ and $t$ can be exponential in the size of $G$. Therefore, we would naturally like avoid actually computing all the shortest $s$-$t$ paths. I don't know about the general case, but it seems to me that we can achieve this for some special graph classes.

This feels like something someone must have considered before. Is there any existing research into this, or is this in fact simple to do even for general graphs?

Asked By : Juho

Answered By : Realz Slaw

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$

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 $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 "left to right".
• 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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17917