pgr_dijkstra - Shortest Path Dijkstra¶

• pgr_dijkstra - Dijkstra’s algorithm for the shortest paths.
• pgr_dijkstraCost -Get the aggregate cost of the shortest paths.

The problem definition¶

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} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \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} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \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{ if } directed = true \\ G_u(V,E) &\quad \text{ if } 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.