Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

Previous versions of this page

Bidirectional Dijkstra - Family of functions

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

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

  • Running time (worse case scenario): O((VlogV+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