## Dijkstra - Family of functions

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.

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