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(\(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