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} &\{(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:
\[\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.
