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.

pgr_dijkstraVia - Propuesto - Obtenga una ruta a partir de una secuencia de vértices.
pgr_dijkstraNear - Propuesto - Obtener la ruta al vértice más cercano.
pgr_dijkstraNearCost - Propuesto - Consigue el costo del vértice más cercano.

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 partida.
`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)\}\)

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

el 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:

el 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