Dijkstra  Family of functions  pgRouting Manual (3.4)
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 ANYINTEGER and ANYNUMERICAL

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.

pgr_dijkstraNear  Proposed  Get the route to the nearest vertex.

pgr_dijkstraNearCost  Proposed  Get the cost to the nearest vertex.
Introduction
Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with nonnegative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.
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: \(O( start\ vids * (V \log V + E))\)
The Dijkstra family functions are based on the Dijkstra algorithm.
Parameters
Column 
Type 
Description 


Edges SQL as described below 


Combinations SQL as described below 

start vid 

Identifier of the starting vertex of the path. 
start vids 

Array of identifiers of starting vertices. 
end vid 

Identifier of the ending vertex of the path. 
end vids 

Array of identifiers of ending vertices. 
Optional parameters
Column 
Type 
Default 
Description 





Inner Queries
Edges SQL
Column 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge (



ANYNUMERICAL 
1 
Weight of the edge (

Where:
 ANYINTEGER :

SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL :

SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations SQL
Parameter 
Type 
Description 


ANYINTEGER 
Identifier of the departure vertex. 

ANYINTEGER 
Identifier of the arrival vertex. 
Where:
 ANYINTEGER :

SMALLINT
,INTEGER
,BIGINT
Advanced documentation
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_{k1}, 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