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.
The following algorithms are based on pgr_dijkstra
- pgr_dijkstraCost - Get the aggregate cost of the shortest paths.
- pgr_drivingDistance - Get catchament information.
- pgr_ksp - Get the aggregate cost of the shortest paths.
The problem definition (Advanced documentation)¶
Given the following query:
pgr_dijkstra(sql,startvid,endvid,directed)
where sql={(idi,sourcei,targeti,costi,reverse_costi)}
and
- source=⋃sourcei,
- target=⋃targeti,
The graphs are defined as follows:
Directed graph
The weighted directed graph, Gd(V,E), is definied by:
- the set of vertices V
- V=source∪target∪startvid∪endvid
- the set of edges E
- E={{(sourcei,targeti,costi) when cost>=0} if reverse_cost=∅{(sourcei,targeti,costi) when cost>=0}∪{(targeti,sourcei,reverse_costi) when reverse_costi>=0)} if reverse_cost≠∅
Undirected graph
The weighted undirected graph, Gu(V,E), is definied by:
- the set of vertices V
- V=source∪target∪startvvid∪endvid
- the set of edges E
- E={{(sourcei,targeti,costi) when cost>=0}∪{(targeti,sourcei,costi) when cost>=0} if reverse_cost=∅{(sourcei,targeti,costi) when cost>=0}∪{(targeti,sourcei,costi) when cost>=0}∪{(targeti,sourcei,reverse_costi) when reverse_costi>=0)}∪{(sourcei,targeti,reverse_costi) when reverse_costi>=0)} if reverse_cost≠∅
The problem
Given:
- startvid∈V a starting vertex
- endvid∈V an ending vertex
- G(V,E)={Gd(V,E) if directed=trueGu(V,E) if directed=false
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.