Is there any implementation of bidirectional search for Dijkstra algorithm?

java algorithm graph-theory dijkstra shortest-path
Fabien picture Fabien · May 28, 2012 · Viewed 8.6k times · Source

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:

enter image description here

Answer

coderodde picture coderodde · Mar 21, 2016

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.)

Related questions

Sample Directed Graph and Topological Sort Code

Anyone know where I can obtain a sample implementation of a Directed Graph and sample code for performing a topological sort on a directed graph? (preferably in Java)

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More