Bidirectional Dijkstra  Family of functions  pgRouting Manual (3.4)
Previous versions of this page
Bidirectional Dijkstra  Family of functions

pgr_bdDijkstra  Bidirectional Dijkstra algorithm for the shortest paths.

pgr_bdDijkstraCost  Bidirectional Dijkstra to calculate the cost of the shortest paths

pgr_bdDijkstraCostMatrix  Bidirectional Dijkstra algorithm to create a matrix of costs of the shortest paths.
Synopsis
Based on Dijkstra’s algorithm, the bidirectional search finds a shortest path a starting vertex to an ending vertex.
It runs two simultaneous searches: one forward from the source, and one backward from the target, stopping when the two meet in the middle.
This implementation can be used with a directed graph and an undirected graph.
Characteristics
The main Characteristics are:

Process is done only on edges with positive costs.

A negative value on a cost column is interpreted as the edge does not exist.


Values are returned when there is a path.

When there is no path:

When the starting vertex and ending vertex are the same.

The aggregate cost of the non included values \((v, v)\) is \(0\)


When the starting vertex and ending vertex are the different and there is no path:

The aggregate cost the non included values \((u, v)\) is \(\infty\)



For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

Running time (worse case scenario): \(O((V \log V + E))\)

For large graphs where there is a path bewtween the starting vertex and ending vertex:

It is expected to terminate faster than pgr_dijkstra

See Also
Indices and tables