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 2.4 2.3 2.2

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.

Experimental

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_dijkstraNear - Experimental - Get the route to the nearest vertex.
pgr_dijkstraNearCost - Experimental - Get the cost to the nearest vertex.

The problem definition (Advanced documentation)¶

Given the following query:

pgr_dijkstra( $s q l, s t a r t_{v i d}, e n d_{v i d}, d i r e c t e d$ )

where $s q l = {(i d_{i}, s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}, r e v e r s e_c o s t_{i})}$

and

$s o u r c e = ⋃ s o u r c e_{i}$ ,
$t a r g e t = ⋃ t a r g e t_{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 = s o u r c e \cup t a r g e t \cup s t a r t_{v i d} \cup e n d_{v i d}$
the set of edges $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

Undirected graph

The weighted undirected graph, $G_{u} (V, E)$ , is definied by:

the set of vertices $V$
- $V = s o u r c e \cup t a r g e t \cup s t a r t_{v} v i d \cup e n d_{v i d}$
the set of edges $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} \\ \cup {(s o u r c e_{i}, t a r g e t_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

The problem

Given:

$s t a r t_{v i d} \in V$ a starting vertex
$e n d_{v i d} \in V$ an ending vertex
$G (V, E) = {\begin{cases} G_{d} (V, E) & if6 d i r e c t e d = t r u e \\ G_{u} (V, E) & if5 d i r e c t e d = f a l s e \end{cases}$

Then:

$π = {(p a t h_s e q_{i}, n o d e_{i}, e d g e_{i}, c o s t_{i}, a g g_c o s t_{i})}$

where:

$p a t h_s e q_{i} = i$
$p a t h_s e q_{| π |} = | π |$
$n o d e_{i} \in V$
$n o d e_{1} = s t a r t_{v i d}$
$n o d e_{| π |} = e n d_{v i d}$
$\forall i \neq | π |, (n o d e_{i}, n o d e_{i + 1}, c o s t_{i}) \in E$
$e d g e_{i} = {\begin{cases} i d_{(n o d e_{i}, n o d e_{i + 1}, c o s t_{i})} & when i \neq | π | \\ - 1 & when i = | π | \end{cases}$
$c o s t_{i} = c o s t_{(n o d e_{i}, n o d e_{i + 1})}$
$a g g_c o s t_{i} = {\begin{cases} 0 & when i = 1 \\ \sum_{k = 1}^{i} c o s t_{(n o d e_{k - 1}, n o d e_{k})} & when i \neq 1 \end{cases}$

In other words: The algorithm returns a the shortest path between $s t a r t_{v i d}$ and $e n d_{v i d}$ , if it exists, in terms of a sequence of nodes and of edges,

$p a t h_s e q$ indicates the relative position in the path of the $n o d e$ or $e d g e$ .
$c o s t$ is the cost of the edge to be used to go to the next node.
$a g g_c o s t$ is the cost from the $s t a r t_{v i d}$ up to the node.

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

Dijkstra - Family of functions¶

The problem definition (Advanced documentation)¶

See Also¶