So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.
So let $l(u,v)$ be length of the (oriented) edge $u,v$, $\pi_f(v)$ the potential of vertex $v$ in forward search and $\pi_r(v)$ potential of vertex $v$ in reverse search and $d(u,v)$ length of the shortest path from $u$ to $v$. Let $s$ be start vertex, $t$ goal vertex. The algorithm selects vertices by $d(s,v)+\pi_f(v)$ forward and $d(v,t)+\pi_r(v)$ reverse.
Let's call $\mu$ the length of the shortest path found so far, $n_f$ the vertex on top of forward queue and $n_r$ the vertex on top of reverse queue. I found two ways
The obvious option is to stop forward when $d(s,n_f)+\pi_f(n_f)\geq\mu$ and reverse when $d(n_r,t)+\pi_r(n_r)\geq\mu$. It is also not needed to process edges that were already processed in the other direction. Here the $\pi_f$ and $\pi_r$ are independent can be very specific, but the algorithm may need to continue quite long after the shortest path was actually found if the potential function is significantly underestimating.
Create a pair of consistent potential functions as defined in this lecture. The requirements are given as $$\pi_f(u) + \pi_r(u) == \pi_f(v) + \pi_r(v)$$ for each edge $u,w$ (which really means the sum has to be constant over the whole graph). Without loss of generality we can make $\pi_r(v) = -\pi_f(v)$ and use the normal stopping condition from non-goal-directed search expressed as $$d(s,m_f)+\pi_f(m_f) + d(m_r,t)+\pi_r(m_r) \geq \mu+\pi_r(t)$$ (assuming we shift $\pi$ so that $\pi_f(s) = 0$).
This allows easier stop, but the potential function has to only indicate whether $v$ is closer to start or goal and for vertex (equally) far from both will be the same as for vertex in the middle of the shortest path. Therefore it will be less specific.
Now what I am looking for is:
- anything that would give me idea which would be more efficient (without having to implement both and test them) and
- whether the second can even be used if the heuristics is not monotonous, i.e. when $d(u,v) - \pi_f(u) + \pi_f(v) \ge 0$ does not hold (the linked lecture assumes that, but not doing so could save me a lot of data and I/O is a bottleneck, so I would prefer not to even though it means occasionally having to reprocess vertex).
1Some important optimization techniques can only be applied to bidirectional search.