Is there any implementation of bidirectional searc

Question

I am looking for an implementation of bidirectional search (a.k.a. "meet in the middle" algorithm) for Dijkstra (or any other source-to-destination shortest path algorithm) in Java.

As bidirectional search processing is trickier than it looks like (Graph Algorithms, p.26), I want to consider an existing implementation before reinventing the wheel!

P.S.: I am talking about bidirectional search, not to be confused with a bidirectional graph)

Here is an example of a tricky graph:

Answer 1

Yes, there is at least in Java: https://github.com/coderodde/GraphSearchPal/blob/master/src/main/java/net/coderodde/gsp/model/support/BidirectionalDijkstraPathFinder.java

In a bidirectional Dijkstra's algorithm, you maintain actually two "Dijkstra's algorithms": the forward search and the backward search. Now, the forward search resembles a lot the unidirectional Dijkstra's algorithm. The backward search, however, proceeds in "reversed" fashion. If there is a directed edge (colloquially called an arc) (u, v), the forward search would traverse it from u to v, whereas the backward search would do the same in opposite direction.

Because the two search processes meet (usually) somewhere in between the source node and the target node, we need another termination condition, which in bidirectional Dijkstra's algorithm is

g(top(OPEN_forward)) + g(top(OPEN_backward)) > l

where l is the length of the shortest known so far path between the source and target nodes.

Additional code you might see only in bidirectional version is checking the possibility of shortening a shortest path candidate every time you improve the g value of any node. (The g value of a node u is the shortest (known so far) distance from the node from which the search started to u.)