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.

Introduction

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.

The main characteristics are:

  • Process is done only on edges with positive costs.

    • A negative value on a cost column is interpreted as the edge does not exist.

  • Values are returned when there is a path.

  • When there is no path:

    • When the starting vertex and ending vertex are the same.

      • The aggregate cost of the non included values \((v, v)\) is \(0\)

    • When the starting vertex and ending vertex are the different and there is no path:

      • The aggregate cost the non included values \((u, v)\) is \(\infty\)

  • For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

  • Running time: \(O(| start\ vids | * (V \log V + E))\)

The Dijkstra family functions are based on the Dijkstra algorithm.

Parameters

Column

Type

Description

Edges SQL

TEXT

Edges SQL as described below

Combinations SQL

TEXT

Combinations SQL as described below

start vid

BIGINT

Identifier of the starting vertex of the path.

start vids

ARRAY[BIGINT]

Array of identifiers of starting vertices.

end vid

BIGINT

Identifier of the ending vertex of the path.

end vids

ARRAY[BIGINT]

Array of identifiers of ending vertices.

Optional parameters

Column

Type

default

Description

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

Inner queries

Edges SQL

Column

Type

Default

Description

id

ANY-INTEGER

Identifier of the edge.

source

ANY-INTEGER

Identifier of the first end point vertex of the edge.

target

ANY-INTEGER

Identifier of the second end point vertex of the edge.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Parameter

Type

Description

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Advanced documentation

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.

See Also

Indices and tables