Dijkstra’s algorithm for shortest paths using bidirectional search.
Returns a two-tuple (d,p) where d is the distance and p is the path from the source to the target.
Distances are calculated as sums of weighted edges traversed.
Edges must hold numerical values for XGraph and XDiGraphs. The weights are set to 1 for Graphs and DiGraphs.
In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra.
Ordinary Dijkstra expands nodes in a sphere-like manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume.
This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems).