Dijkstra - Familia de funciones

Propuesto

Advertencia

Funciones propuestas para la próxima versión mayor.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL

    • Es posible que el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Es posible que la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

    • Es posible que la documentación necesite un refinamiento.

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

La definición de problema (Documentación avanzada)

Dada la siguiente consulta:

pgr_dijkstra(\(sql, start_{vid}, end_{vid}, directed\))

Donde \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)

y

  • \(source = \bigcup source_i\),

  • \(target = \bigcup target_i\),

Los gráficos se definen como sigue:

Grafo dirigido

El gráfico dirigido ponderado, \(G_d(V,E)\), se define por:

  • Conjunto de vértices \(V\)

    • \(V = source \cup target \cup {start_{vid}} \cup {end_{vid}}\)

  • El conjunto de aristas \(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}\)

Grafo no dirigido

El grafo ponderado no dirigido \(G_u(V,E)\), es definido por:

  • Conjunto de vértices \(V\)

    • \(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)

  • El conjunto de aristas \(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}\)

El problema

Dado:

  • \(start_{vid} \in V\) a starting vertex

  • \(end_{vid} \in V\) un vértice final

  • \(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}\)

Entonces:

  • \(\boldsymbol{\pi} = \{(path\_seq_i, node_i, edge_i, cost_i, agg\_cost_i)\}\)

Donde:
  • \(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\) indica la posición relativa en el camino de \(node\) o \(edge\).

  • \(cost\) es el coste del borde que se utilizará para ir al siguiente nodo.

  • \(agg\_cost\) es el costo desde el \(start_{vid}\) hasta el nodo.

Si no hay ruta, el conjunto resultante estará vacío.

Ver también

Índices y tablas