# pgRouting Manual (3.6)

## Bidirectional Dijkstra - Family of functions

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

- Index

- Search Page