Bidirectional Dijkstra - Family of functions¶

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

• Index
• Search Page