pgr_bdDijkstra¶

pgr_bdDijkstra — Devuelve la(s) rutas más cortas mediante el algoritmo Bidirectional Dijkstra.

_images/boost-inside.jpeg — Adentro: Boost Graph¶

Disponibilidad:

Versión 3.2.0
- Nueva función propuesta:
  - pgr_bdDijkstra(Combinaciones)
Versión 3.0.0
- Función oficial
Versión 2.5.0
- Nuevas funciones Propuestas:
  - pgr_bdDijkstra(Uno a Muchos)
  - pgr_bdDijkstra(Muchos a Uno)
  - pgr_bdDijkstra(Muchos a Muchos)
Versión 2.4.0
- La firma cambió en pgr_bdDijsktra(Uno a Uno)
  - Firma antigua ya no soportada
Versión 2.0.0
- Oficial pgr_bdDijkstra(Uno a Uno)

Descripción¶

Las características principales son:

El proceso se realiza sólo en las aristas con costos positivos.
Valores son regresados cuando hay un camino.
Cuando el vértice inicial y el vértice final son iguales, no hay camino.
- El agg_cost de los valores no incluídos (v, v) es 0
Cuando el vértice inicial y el vértice final son diferentes y no hay camino:
- El “agg_cost” de los valores no incluídos “(u, v)” es :math: infty
Tiempo de ejecución (peor de los casos): \(O((V \log V + E))\)
Para grandes gráficos donde hay un camino entre el vértice inicial y el vértice final:
- Se espera que termine más rápido que pgr_dijkstra

Firmas¶

Resumen

pgr_bdDijkstra(Edges SQL, start_vid,  end_vid  [, directed])
pgr_bdDijkstra(Edges SQL, start_vid,  end_vids [, directed])
pgr_bdDijkstra(Edges SQL, start_vids, end_vid  [, directed])
pgr_bdDijkstra(Edges SQL, start_vids, end_vids [, directed])
pgr_bdDijkstra(Edges SQL, Combinations SQL [, directed]) -- Proposed on v3.2

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET

Uso de valores predeterminados

pgr_bdDijkstra(Edges SQL, start_vid, end_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: Del vértice \(2\) al vértice \(3\)

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, 3
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   16 |    1 |        3
   5 |        5 |    4 |    3 |    1 |        4
   6 |        6 |    3 |   -1 |    0 |        5
(6 rows)

Uno a Uno¶

pgr_bdDijkstra(Edges SQL, start_vid, end_vid [, directed])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: Del vértice \(2\) al vértice \(3\) en un grafo no dirigido

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, 3,
    false
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    2 |    1 |        0
   2 |        2 |    3 |   -1 |    0 |        1
(2 rows)

Uno a Muchos¶

pgr_bdDijkstra(Edges SQL, start_vid, end_vids [, directed])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: Del vértice \(2\) a los vértices \(\{3, 11\}\) en un grafo dirigido

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, ARRAY[3, 11]);
 seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |       3 |    2 |    4 |    1 |        0
   2 |        2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |       3 |    6 |    9 |    1 |        2
   4 |        4 |       3 |    9 |   16 |    1 |        3
   5 |        5 |       3 |    4 |    3 |    1 |        4
   6 |        6 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |      11 |    2 |    4 |    1 |        0
   8 |        2 |      11 |    5 |    8 |    1 |        1
   9 |        3 |      11 |    6 |   11 |    1 |        2
  10 |        4 |      11 |   11 |   -1 |    0 |        3
(10 rows)

Muchos a Uno¶

pgr_bdDijkstra(Edges SQL, start_vids, end_vid [, directed])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: De los vértices \(\{2, 7\}\) al vértice \(3\) en un grafo dirigido

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2, 7], 3);
 seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
   1 |        1 |         2 |    2 |    4 |    1 |        0
   2 |        2 |         2 |    5 |    8 |    1 |        1
   3 |        3 |         2 |    6 |    9 |    1 |        2
   4 |        4 |         2 |    9 |   16 |    1 |        3
   5 |        5 |         2 |    4 |    3 |    1 |        4
   6 |        6 |         2 |    3 |   -1 |    0 |        5
   7 |        1 |         7 |    7 |    6 |    1 |        0
   8 |        2 |         7 |    8 |    7 |    1 |        1
   9 |        3 |         7 |    5 |    8 |    1 |        2
  10 |        4 |         7 |    6 |    9 |    1 |        3
  11 |        5 |         7 |    9 |   16 |    1 |        4
  12 |        6 |         7 |    4 |    3 |    1 |        5
  13 |        7 |         7 |    3 |   -1 |    0 |        6
(13 rows)

Muchos a Muchos¶

pgr_bdDijkstra(Edges SQL, start_vids, end_vids [, directed])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: De los vértices \(\{2, 7\}\) a los vértices \(\{3, 11\}\) en un grafo dirigido

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2, 7], ARRAY[3, 11]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
|        1 |         2 |       3 |    2 |    4 |    1 |        0
|        2 |         2 |       3 |    5 |    8 |    1 |        1
|        3 |         2 |       3 |    6 |    9 |    1 |        2
|        4 |         2 |       3 |    9 |   16 |    1 |        3
|        5 |         2 |       3 |    4 |    3 |    1 |        4
|        6 |         2 |       3 |    3 |   -1 |    0 |        5
|        1 |         2 |      11 |    2 |    4 |    1 |        0
|        2 |         2 |      11 |    5 |    8 |    1 |        1
|        3 |         2 |      11 |    6 |   11 |    1 |        2
|        4 |         2 |      11 |   11 |   -1 |    0 |        3
|        1 |         7 |       3 |    7 |    6 |    1 |        0
|        2 |         7 |       3 |    8 |    7 |    1 |        1
|        3 |         7 |       3 |    5 |    8 |    1 |        2
|        4 |         7 |       3 |    6 |    9 |    1 |        3
|        5 |         7 |       3 |    9 |   16 |    1 |        4
|        6 |         7 |       3 |    4 |    3 |    1 |        5
|        7 |         7 |       3 |    3 |   -1 |    0 |        6
|        1 |         7 |      11 |    7 |    6 |    1 |        0
|        2 |         7 |      11 |    8 |    7 |    1 |        1
|        3 |         7 |      11 |    5 |   10 |    1 |        2
|        4 |         7 |      11 |   10 |   12 |    1 |        3
|        5 |         7 |      11 |   11 |   -1 |    0 |        4
(22 rows)

Combinaciones¶

pgr_bdDijkstra(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo: Uso de una tabla de combinaciones en un grafo dirigido.

SELECT * FROM pgr_bdDijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    'SELECT * FROM ( VALUES (2, 3), (7, 11) ) AS t(source, target)');
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         2 |       3 |    2 |    4 |    1 |        0
   2 |        2 |         2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |         2 |       3 |    6 |    9 |    1 |        2
   4 |        4 |         2 |       3 |    9 |   16 |    1 |        3
   5 |        5 |         2 |       3 |    4 |    3 |    1 |        4
   6 |        6 |         2 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |         7 |      11 |    7 |    6 |    1 |        0
   8 |        2 |         7 |      11 |    8 |    7 |    1 |        1
   9 |        3 |         7 |      11 |    5 |   10 |    1 |        2
  10 |        4 |         7 |      11 |   10 |   12 |    1 |        3
  11 |        5 |         7 |      11 |   11 |   -1 |    0 |        4
(11 rows)

Parámetros¶

Parámetro	Tipo	Valores predeterminados	Descripción
Edges SQL	`TEXT`		Consulta de bordes como se describe a continuación
Combinaciones SQL	`TEXT`		Consulta de combinaciones como se describe a continuación
start_vid	`BIGINT`		Identificador del vértice inicial de la ruta.
start_vids	`ARRAY[BIGINT]`		Arreglo de identificadores de vértices iniciales.
end_vid	`BIGINT`		Identificador del vértice final de la ruta.
end_vids	`ARRAY[BIGINT]`		Arreglo de identificadores de vértices finales.
dirigido	`BOOLEAN`	`true`	Cuando `true` el gráfo se considera Dirigido Cuando `false` el gráfo se considera No Dirigido

Consultas internas¶

Consulta de aristas¶

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
costo	`ANY-NUMERICAL`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	`ANY-NUMERICAL`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consulta de combinaciones¶

Columna	Tipo	Valores predeterminados	Descripción
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Columnas de Resultados¶

Devuelve el conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	`INT`	Valor secuencial a partir de 1.
path_id	`INT`	Identificador de ruta. Tiene el valor 1 para el primero de una ruta. Se utiliza cuando hay varias rutas para la misma combinación de `start_vid` a `end_vid`.
path_seq	`INT`	Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.
start_vid	`BIGINT`	Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. Muchos a Uno Muchos a Muchos
end_vid	`BIGINT`	Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. Uno a Muchos Muchos a Muchos
nodo	`BIGINT`	Identificador del nodo en la ruta de `start_vid` a `end_vid`.
arista	`BIGINT`	Identificador del borde utilizado para ir del `nodo` al siguiente nodo de la secuencia de ruta. `-1` para el último nodo de la ruta.
costo	`FLOAT`	Costo de desplazamiento desde `node` usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	`FLOAT`	Coste agregado de `start_v` to `node`.

Ver también¶

Las consultas utilizan la red Datos Muestra .
Bidirectional Dijkstra - Familia de funciones
https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf
https://en.wikipedia.org/wiki/Bidirectional_search

Índices y tablas