# pgRouting Manual (3.0-rc1)

## Dijkstra - Family of functions

- pgr_dijkstra - Dijkstra’s algorithm for the shortest paths.
- pgr_dijkstraCost - Get the aggregate cost of the shortest paths.
- pgr_dijkstraCostMatrix - Use pgr_dijkstra to create a costs matrix.
- pgr_drivingDistance - Use pgr_dijkstra to calculate catchament information.
- pgr_KSP - Use Yen algorithm with pgr_dijkstra to get the K shortest paths.

proposed

Warning

Proposed functions for next mayor release.

- They are not officially in the current release.
- They will likely officially be part of the next mayor release:
  - The functions make use of ANY-INTEGER and ANY-NUMERICAL
  - Name might not change. (But still can)
  - Signature might not change. (But still can)
  - Functionality might not change. (But still can)
  - pgTap tests have being done. But might need more.
  - Documentation might need refinement.

- pgr_dijkstraVia - Proposed - Get a route of a seuence of vertices.

Previous versions of this page

- Supported versions: current(3.0) 2.6
- Unsupported versions: 2.5 2.4 2.3 2.2

## The problem definition (Advanced documentation)

Given the following query:

pgr_dijkstra(\(sql, start_{vid}, end_{vid}, directed\))

where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)

and

- \(source = \bigcup source_i\),
- \(target = \bigcup target_i\),

The graphs are defined as follows:

Directed graph

The weighted directed graph, \(G_d(V,E)\), is definied by:

- the set of vertices \(V\)
  - \(V = source \cup target \cup {start_{vid}} \cup {end_{vid}}\)
- the set of edges \(E\)
  - \(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \quad \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i>=0 \} & \quad \text{if } reverse\_cost \neq \varnothing \\ \end{cases}\)

Undirected graph

The weighted undirected graph, \(G_u(V,E)\), is definied by:

- the set of vertices \(V\)
  - \(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)
- the set of edges \(E\)
  - \(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \text{ } \\ \cup \{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)

The problem

Given:

- \(start_{vid} \in V\) a starting vertex
- \(end_{vid} \in V\) an ending vertex
- \(G(V,E) = \begin{cases} G_d(V,E) & \quad \text{ if6 } directed = true \\ G_u(V,E) & \quad \text{ if5 } directed = false \\ \end{cases}\)

Then:

- \(\boldsymbol{\pi} = \{(path\_seq_i, node_i, edge_i, cost_i, agg\_cost_i)\}\)

where:
  - \(path\_seq_i = i\)
  - \(path\_seq_{| \pi |} = | \pi |\)
  - \(node_i \in V\)
  - \(node_1 = start_{vid}\)
  - \(node_{| \pi |} = end_{vid}\)
  - \(\forall i \neq | \pi |, \quad (node_i, node_{i+1}, cost_i) \in E\)
  - \(edge_i = \begin{cases} id_{(node_i, node_{i+1},cost_i)} &\quad \text{when } i \neq | \pi | \\ -1 &\quad \text{when } i = | \pi | \\ \end{cases}\)
  - \(cost_i = cost_{(node_i, node_{i+1})}\)
  - \(agg\_cost_i = \begin{cases} 0 &\quad \text{when } i = 1 \\ \displaystyle\sum_{k=1}^{i} cost_{(node_{k-1}, node_k)} &\quad \text{when } i \neq 1 \\ \end{cases}\)
In other words: The algorithm returns a the shortest path between \(start_{vid}\) and \(end_{vid}\) , if it exists, in terms of a sequence of nodes and of edges,
  - \(path\_seq\) indicates the relative position in the path of the \(node\) or \(edge\).
  - \(cost\) is the cost of the edge to be used to go to the next node.
  - \(agg\_cost\) is the cost from the \(start_{vid}\) up to the node.

If there is no path, the resulting set is empty.

## See Also

Indices and tables

- Index
- Search Page