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.

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