Is there a bi-directional implementation of the Dijkstra algorithm?

Question

I am looking for a bidirectional search implementation (aka "Meeting in the middle" algorithm) for Dijkstra (or any other shortest path algorithm from source to destination) in Java.

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

PS: I'm talking about bidirectional search , so as not to be confused with a bidirectional schedule)

Here is an example of a complex schedule:

Answer 1

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

In Dijkstra's bidirectional algorithm, you actually support two "Dijkstra's algorithms": forward search and reverse search. Now advanced search is very similar to Dijkstra's unidirectional algorithm. However, the search in reverse order occurs "in the opposite way." If there is a directed edge (colloquially called arc ) (u, v) , the direct search will go from u to v , while the reverse search will do the same in the opposite direction.

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

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

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

An additional code that you can only see in the bidirectional version is to check the possibility of shortening the smallest candidate path each , when you improve the g value of any node, (The value of g a node u is the shortest (known so far) distance from node, from whose search began with u .)