pgr_dijkstraNear
- Propuesto¶
pgr_dijkstraNear
— Utilizando el algoritmo dijkstra, encuentra la ruta que conduce al vértice más cercano.
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.
Disponibilidad
Versión 3.3.0
Promovido a función propuesta
Versión 3.2.0
Nueva función experimental
Descripción¶
Dado un grafo, un vértice inicial y un conjunto de vértices finales, esta función encuentra la ruta más corta desde el vértice inicial hasta el vértice final más cercano.
Características¶
Utiliza el algoritmo Dijkstra.
Funciona para grafos dirigidos y no dirigidos.
Cuando hay más de una ruta al mismo vértice con el mismo coste:
El algoritmo devolverá solo una ruta
Opcionalmente permite encontrar más de una ruta.
Cuando se va a devolver más de una ruta:
Los resultados se ordenan en orden creciente de:
costo agregado
Dentro del mismo valor de los costes agregados:
los resultados se ordenan por (fuente, destino)
Tiempo de ejecución: Dijkstra tiempo de ejecución: \(drt = O((|E| + |V|)log|V|)\)
Uno a Muchos; \(drt\)
Muchos a Uno: \(drt\)
Muchos a Muchos: \(drt * |Starting vids|\)
Combinaciones: \(drt * |Starting vids|\)
Firmas¶
Resumen
[directed, cap]
[directed, cap, global]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Uno a Muchos¶
[directed, cap]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Saliendo en coche desde el vértice \(6\) encontrar la estación de metro más cercana.
Usando un grafo dirigido para el ruteo de automóviles.
Las estaciones de metro se encuentran en los siguientes vértices \(\{1, 10, 11\}\)
Los valores predeterminados utilizados:
directed => true
cap => 1
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 6, ARRAY[10, 11, 1]);
4 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
5-----+----------+-----------+---------+------+------+------+----------
6 1 | 1 | 6 | 11 | 6 | 4 | 1 | 0
7 2 | 2 | 6 | 11 | 7 | 8 | 1 | 1
8 3 | 3 | 6 | 11 | 11 | -1 | 0 | 2
9(3 rows)
10
El resultado muestra que la estación en el vértice \(11\) es la más cercana.
Muchos a Uno¶
[directed, cap]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Saliendo en coche desde una estación de metro encontrar las dos estaciones más cercanas al vértice \(2\)
Usando un grafo dirigido para el ruteo de automóviles.
Las estaciones de metro se encuentran en los siguientes vértices \(\{1, 10, 11\}\)
En la línea 4: utilizando el parámetro posicional: directed configurado en
true
En la línea 5: usando el parámetro con nombre cap => 2
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[10, 11, 1], 6,
4 true,
5 cap => 2);
6 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
7-----+----------+-----------+---------+------+------+------+----------
8 1 | 1 | 10 | 6 | 10 | 2 | 1 | 0
9 2 | 2 | 10 | 6 | 6 | -1 | 0 | 1
10 3 | 1 | 11 | 6 | 11 | 8 | 1 | 0
11 4 | 2 | 11 | 6 | 7 | 4 | 1 | 1
12 5 | 3 | 11 | 6 | 6 | -1 | 0 | 2
13(5 rows)
14
El resultado muestra que la estación en el vértice \(10\) es la más cercana y la siguiente mejor es \(11\).
Muchos a Muchos¶
[directed, cap, global]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Encuentra la mejor conexión peatonal entre dos líneas de autobuses
Usando un grafo no dirigido para el ruteo de peatones
Las estaciones de la primera línea de metro están en \(\{15, 16\}\)
Las estaciones de la segunda línea de metro están en \(\{1, 10, 11\}\)
En la línea 4: utilizando el parámetro con nombre: directed => false
Los valores predeterminados utilizados:
cap => 1
global => true
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[15, 16], ARRAY[10, 11, 1],
4 directed => false);
5 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
6-----+----------+-----------+---------+------+------+------+----------
7 1 | 1 | 15 | 10 | 15 | 3 | 1 | 0
8 2 | 2 | 15 | 10 | 10 | -1 | 0 | 1
9(2 rows)
10
Para un peatón la mejor conexión es subir/bajar en el vértice \(15\) de la primera línea de metro y en el vértice \(10\) de la segunda línea de metro.
Solo se devuelve una ruta porque global es true
y cap es 1
Combinaciones¶
[directed, cap, global]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Encuentra la mejor conexión de coche entre todas las estaciones de dos líneas de metro
Usando un grafo dirigido para el ruteo de automóviles.
Las estaciones de la primera línea de metro están en \(\{1, 10, 11\}\)
Las estaciones de la segunda línea de metro están en \(\{15, 16\}\)
El contenido de las combinaciones:
SELECT unnest(ARRAY[10, 11, 1]) as source, target
FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
UNION
SELECT unnest(ARRAY[15, 16]), target
FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b ORDER BY source, target;
source | target
--------+--------
1 | 15
1 | 16
10 | 15
10 | 16
11 | 15
11 | 16
15 | 1
15 | 10
15 | 11
16 | 1
16 | 10
16 | 11
(12 rows)
La consulta:
líneas 3~4 establece los vértices de inicio de la primera línea de metro y los vértices finales de la segunda línea de metro
la línea 6~7 establecen los vértices de inicio de la primera línea de metro y los vértices finales de la primera línea de metro
En la línea 8: usando el parámetro con nombre global => false
Los valores predeterminados utilizados:
directed => true
cap => 1
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 'SELECT unnest(ARRAY[10, 11, 1]) as source, target
4 FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
5 UNION
6 SELECT unnest(ARRAY[15, 16]), target
7 FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b',
8 global => false);
9 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
10-----+----------+-----------+---------+------+------+------+----------
11 1 | 1 | 11 | 16 | 11 | 9 | 1 | 0
12 2 | 2 | 11 | 16 | 16 | -1 | 0 | 1
13 3 | 1 | 15 | 10 | 15 | 3 | 1 | 0
14 4 | 2 | 15 | 10 | 10 | -1 | 0 | 1
15 5 | 1 | 16 | 11 | 16 | 9 | 1 | 0
16 6 | 2 | 16 | 11 | 11 | -1 | 0 | 1
17 7 | 1 | 10 | 16 | 10 | 5 | 1 | 0
18 8 | 2 | 10 | 16 | 11 | 9 | 1 | 1
19 9 | 3 | 10 | 16 | 16 | -1 | 0 | 2
20 10 | 1 | 1 | 16 | 1 | 6 | 1 | 0
21 11 | 2 | 1 | 16 | 3 | 7 | 1 | 1
22 12 | 3 | 1 | 16 | 7 | 8 | 1 | 2
23 13 | 4 | 1 | 16 | 11 | 9 | 1 | 3
24 14 | 5 | 1 | 16 | 16 | -1 | 0 | 4
25(14 rows)
26
A partir de los resultados:
haciendo una conexión desde la primera línea de metro \(\{1, 10, 11\}\) a la segunda \(\{15, 16\}\):
Las mejores conecciones de todas las estaciones desde la primera línea son: \({(1 \rightarrow 16) (10 \rightarrow 16) (11 \rightarrow 16)}\)
La mejor es:math:(11 rightarrow 16) con un costo de \(1\) (líneas: 11 y 12)
haciendo una conexión desde la segunda línea de metro \(\{15, 16\}\) a la primera \(\{1, 10, 11\}\):
Las mejores conecciones de todas las estaciones desde la segunda línea son: \({(15 \rightarrow 10) (16 \rightarrow 11)}\)
Ambas son igualmente buenas, como también tienen el mismo costo. (lines: 13 and 14 and lines: 15 and 16)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
SQL de aristas como se describe a continuación |
|
|
SQL de combinaciones como se describe a abajo |
|
salida |
|
Identificador del vértice inicial de la ruta. |
salidas |
|
Arreglo de identificadores de vértices iniciales. |
destino |
|
Identificador del vértice final de la ruta. |
destinos |
|
Arreglo de identificadores de vértices finales. |
Parámetros opcionales de Dijkstra¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Parámetros opcionales de Cercanía¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
Encuentra como máximo el número |
|
|
|
|
Consultas Internas¶
SQL aristas¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL Combinaciones¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
ENTEROS |
Identificador del vértice de salida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Regresa (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del vértice inicial de la ruta actual. |
|
|
Identificador del vértice final de la ruta actual. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Ver también¶
boost: https://www.boost.org/libs/graph/doc/table_of_contents.html
Wikipedia: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Índices y tablas