Dijkstra - Familia de funciones

  • pgr_dijkstra - Algoritmo de Dijkstra para las rutas más cortas.

  • pgr_dijkstraCost - Obtener el costo agregado de las rutas más cortas.

  • pgr_dijkstraCostMatrix - Usar pgr_dijkstra para crear una matriz de costes.

  • pgr_drivingDistance - Usar pgr_dijkstra para calcular información de captación.

  • pgr_KSP - Usar el algoritmo Yen con pgr_dijkstra para obtener las K rutas más cortas.

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 ENTEROS y FLOTANTES

    • Probablemente el nombre no cambie. (Pero todavía puede)

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

    • Probablemente 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.

Introducción

Algoritmo de Dijkstra, concebido por el informático holandés Edsger Dijkstra en 1956. Es un algoritmo de búsqueda en grafos que resuelve el problema de ruta más corta para un grafo con costos de aristas no negativos, produciendo la ruta más corta desde un vértice inicial a un vértice final . Esta implementación se puede utilizar con un grafos dirigidos y no dirigidos.

Las principales características son:

  • El proceso se realiza sólo en aristas con costos positivos.

    • Valor no negativo en una columna de costo se interpreta como la arista no exite.

  • Los valores se devuelven cuando hay una ruta.

  • Cuando no hay ruta:

    • Cuando el vértice de salida y el vértice destino son iguales.

      • El costo agregado de los valores no incluídos \((v, v)\) es \(0\)

    • Cuando el vértice de salida y el vértice destino son diferentes y no hay ninguna ruta:

      • El costo agregado de los valores no incluídos \((u, v)\) es :math: infty

  • Para fines de optimización, se ignora cualquier valor duplicado en los vertices de salida o destino.

  • Tiempo de ejecución: \(O(| start\_vids | * (V \log V + E))\)

Las funciones de la familia de Dijkstra se basan en el algoritmo de Dijkstra.

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

BIGINT

Identificador del vértice inicial de la ruta.

salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

destino

BIGINT

Identificador del vértice final de la ruta.

destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Parámetros opcionales

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido.

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL Combinaciones

Parámetro

Tipo

Descripción

source

ENTEROS

Identificador del vértice de salida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Documentación avanzada

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\) un vértice inicial

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

En otras palabras: El algoritmo devuelve la ruta más corta entre \(start_{vid}\) y \(end_{vid}\), si es que existe, en términos de una secuencia de nodos y de aristas,

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