Bidirectional Dijkstra - Family of functions - pgRouting Manual (3.2)
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 (
start_vid
) to an ending vertex (
end_vid
).
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.
-
Values are returned when there is a path.
-
When the starting vertex and ending vertex are the same, there is no path.
-
The agg_cost the non included values (v, v) is 0
-
-
When the starting vertex and ending vertex are the different and there is no path:
-
The agg_cost the non included values (u, v) is \(\infty\)
-
-
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