pgr_dijkstraNearCost
- Propuesto¶
pgr_dijkstraNearCost
— Usando 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.

Adentro: Boost Graph¶
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
pgr_dijkstraNearCost(Edges SQL, start vid, end vids [, directed] [, cap]) pgr_dijkstraNearCost(Edges SQL, start vids, end vid [, directed] [, cap]) pgr_dijkstraNearCost(Edges SQL, start vids, end vids [, directed] [, cap], [global]) pgr_dijkstraNearCost(Edges SQL, Combinations SQL [, directed] [, cap] [, global]) RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET
Uno a Muchos¶
pgr_dijkstraNearCost(Edges SQL, start vid, end vids [, directed] [, cap]) RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET
- 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_dijkstraNearCost(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 6, ARRAY[10, 11, 1]);
4 start_vid | end_vid | agg_cost
5-----------+---------+----------
6 6 | 11 | 2
7(1 row)
8
El resultado muestra que la estación en el vértice \(11\) es la más cercana.
Muchos a Uno¶
pgr_dijkstraNearCost(Edges SQL, start vids, end vid [, directed] [, cap]) RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET
- Ejemplo:
Saliendo en coche desde una estación de metro encontrar las dos estaciones más cercanas al vértice \(6\)
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_dijkstraNearCost(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[10, 11, 1], 6,
4 true,
5 cap => 2) ORDER BY agg_cost;
6 start_vid | end_vid | agg_cost
7-----------+---------+----------
8 10 | 6 | 1
9 11 | 6 | 2
10(2 rows)
11
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¶
pgr_dijkstraNearCost(Edges SQL, start vids, end vids [, directed] [, cap], [global]) RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET
- 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_dijkstraNearCost(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[15, 16], ARRAY[10, 11, 1],
4 directed => false);
5 start_vid | end_vid | agg_cost
6-----------+---------+----------
7 15 | 10 | 1
8(1 row)
9
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¶
pgr_dijkstraNearCost(Edges SQL, Combinations SQL [, directed] [, cap] [, global]) RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET
- 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:
lines 3~4 sets the start vertices to be from the fisrt subway line and the ending vertices to be from the second subway line
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_dijkstraNearCost(
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 start_vid | end_vid | agg_cost
10-----------+---------+----------
11 11 | 16 | 1
12 15 | 10 | 1
13 16 | 11 | 1
14 10 | 16 | 2
15 1 | 16 | 4
16(5 rows)
17
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 \((11 \rightarrow 16)\) con un costo de \(1\) (line: 1)
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)}\)
Ambos son igualmente buenos ya que tienen el mismo costo. (lines: 12 and 13)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
SQL Aristas como se describe a continuación |
|
|
SQL Combinaciones como se describe a abajo |
|
vid de salida |
|
Identificador del vértice inicial de la ruta. |
vid salidas |
|
Arreglo de identificadores de vértices iniciales. |
vid destino |
|
Identificador del vértice final de la ruta. |
vids 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¶
Conjunto de (start_vid, end_vid, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del vértice de salida. |
|
|
Identificador del vértice destino. |
|
|
Costo afregado 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