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.
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 non-negative 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	`TEXT`	Edges SQL as described below
Combinations SQL	`TEXT`	Combinations SQL as described below
start vid	`BIGINT`	Identifier of the starting vertex of the path.
start vids	`ARRAY[BIGINT]`	Array of identifiers of starting vertices.
end vid	`BIGINT`	Identifier of the ending vertex of the path.
end vids	`ARRAY[BIGINT]`	Array of identifiers of ending vertices.

Optional parameters¶

Column	Type	Default	Description
`directed`	`BOOLEAN`	`true`	When `true` the graph is considered Directed When `false` the graph is considered as Undirected.

Inner Queries¶

Edges SQL¶

Column	Type	Default	Description
`id`	ANY-INTEGER		Identifier of the edge.
`source`	ANY-INTEGER		Identifier of the first end point vertex of the edge.
`target`	ANY-INTEGER		Identifier of the second end point vertex of the edge.
`cost`	ANY-NUMERICAL		Weight of the edge (`source`, `target`)
`reverse_cost`	ANY-NUMERICAL	-1	Weight of the edge (`target`, `source`) When negative: edge (`target`, `source`) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL¶

Parameter	Type	Description
`source`	ANY-INTEGER	Identifier of the departure vertex.
`target`	ANY-INTEGER	Identifier of the arrival vertex.

Where:

ANY-INTEGER:: 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_{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.