Processing math: 47%

pgRouting Manual (2.3)

Dijkstra - Family of functions

«  pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path   ::   Contents   ::   pgr_dijkstra  »


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.

The following algorithms are based on pgr_dijkstra

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=sourcetargetstartvidendvid
  • 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=sourcetargetstartvvidendvid
  • 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:

  • startvidV a starting vertex
  • endvidV an ending vertex
  • G(V,E)={Gd(V,E) if directed=trueGu(V,E) if directed=false

Then:

\begin{split}\text{pgr_dijkstra}(sql, start_{vid}, end_{vid}, directed) = \begin{cases} \text{shortest path } \boldsymbol{\pi} \text{ between } start_{vid} \text{and } end_{vid} &\quad \text{if } \exists \boldsymbol{\pi} \\ \varnothing &\quad \text{otherwise} \\ \end{cases}\end{split}

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

«  pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path   ::   Contents   ::   pgr_dijkstra  »