pgr_dijkstra¶
pgr_dijkstra — Devuelve la(s) rutas más cortas mediante el algoritmo Dijkstra. En particular, el algoritmo Dijkstra implementado por Boost.Graph.
Adentro: Boost Graph¶
Disponibilidad
Versión 3.1.0
Nuevas funciones Propuestas:
pgr_dijkstra(combinaciones)
Versión 3.0.0
Funciones oficiales
Version 2.2.0
Nuevas funciones propuestas:
pgr_dijkstra(One to Many)
pgr_dijkstra(Many to One)
pgr_dijkstra(Many to Many)
Versión 2.1.0
Cambio de firma en pgr_dijkstra(Uno a Uno)
Versión 2.0.0
Oficial pgr_dijkstra(Uno a Uno)
Descripción¶
Algoritmo de Dijkstra, concebido por el informático holandés Edsger Dijkstra en 1956. Es un algoritmo de búsqueda de grafos que resuelve el problema de ruta más corta para un grafo con costos de ruta de arista no negativos, produciendo una ruta más corta desde un vértice inicial (start_vid) a un vértice final (end_vid). Esta implementación se puede utilizar con un grafo dirigido y uno no dirigido.
- Las principales características 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
Para fines de optimización, se omite cualquier valor duplicado en start_vids o end_vids.
Los valores regresados se ordenan:
start_vid ascendente
end_vid ascendente
Tiempo de ejecución: \(O(| start\_vids | * (V \log V + E))\)
Firmas¶
Resumen
pgr_dijkstra(Edges SQL, start_vid, end_vid [, directed])
pgr_dijkstra(Edges SQL, start_vid, end_vids [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vid [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vids [, directed])
pgr_dijkstra(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET
Uso de valores predeterminados
pgr_dijkstra(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\) en un grafo dirigido
SELECT * FROM pgr_dijkstra(
'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_dijkstra(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_dijkstra(
'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_dijkstra(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, 5\}\) en un grafo no dirigido
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, ARRAY[3,5],
FALSE
);
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 | 5 | 1 | 2
4 | 4 | 3 | 3 | -1 | 0 | 3
5 | 1 | 5 | 2 | 4 | 1 | 0
6 | 2 | 5 | 5 | -1 | 0 | 1
(6 rows)
Muchos a Uno¶
pgr_dijkstra(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, 11\}\) to vertex \(5\) on a directed graph
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2,11], 5
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | -1 | 0 | 1
3 | 1 | 11 | 11 | 13 | 1 | 0
4 | 2 | 11 | 12 | 15 | 1 | 1
5 | 3 | 11 | 9 | 9 | 1 | 2
6 | 4 | 11 | 6 | 8 | 1 | 3
7 | 5 | 11 | 5 | -1 | 0 | 4
(7 rows)
Muchos a Muchos¶
pgr_dijkstra(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, 11\}\) a los vértices \(\{3, 5\}\) en un grafo no dirigido
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2,11], ARRAY[3,5],
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
3 | 1 | 2 | 5 | 2 | 4 | 1 | 0
4 | 2 | 2 | 5 | 5 | -1 | 0 | 1
5 | 1 | 11 | 3 | 11 | 11 | 1 | 0
6 | 2 | 11 | 3 | 6 | 5 | 1 | 1
7 | 3 | 11 | 3 | 3 | -1 | 0 | 2
8 | 1 | 11 | 5 | 11 | 11 | 1 | 0
9 | 2 | 11 | 5 | 6 | 8 | 1 | 1
10 | 3 | 11 | 5 | 5 | -1 | 0 | 2
(10 rows)
Combinaciones¶
pgr_dijkstra(Edges SQL, Combinations SQL, end_vids, [, 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 no direccionado
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM combinations_table',
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 2 | 1 | 1 | 1 | 0
2 | 2 | 1 | 2 | 2 | -1 | 0 | 1
3 | 1 | 1 | 4 | 1 | 1 | 1 | 0
4 | 2 | 1 | 4 | 2 | 2 | 1 | 1
5 | 3 | 1 | 4 | 3 | 3 | 1 | 2
6 | 4 | 1 | 4 | 4 | -1 | 0 | 3
7 | 1 | 2 | 1 | 2 | 1 | 1 | 0
8 | 2 | 2 | 1 | 1 | -1 | 0 | 1
9 | 1 | 2 | 4 | 2 | 2 | 1 | 0
10 | 2 | 2 | 4 | 3 | 3 | 1 | 1
11 | 3 | 2 | 4 | 4 | -1 | 0 | 2
(11 rows)
Parámetros¶
Parámetro |
Tipo |
Valores predeterminados |
Descripción |
|---|---|---|---|
Edges SQL |
|
Edges query como se describe a continuación |
|
Combinaciones SQL |
|
Combinations query como se describe a continuación |
|
start_vid |
|
Identificador del vértice inicial de la ruta. |
|
start_vids |
|
Arreglo de identificadores de vértices iniciales. |
|
end_vid |
|
Identificador del vértice final de la ruta. |
|
end_vids |
|
Arreglo de identificadores de vértices finales. |
|
dirigido |
|
|
|
Consultas internas¶
Consulta de aristas¶
Columna |
Tipo |
Valores predeterminados |
Descripción |
|---|---|---|---|
id |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
costo |
|
Peso de la arista (source, target)
|
|
reverse_cost |
|
-1 |
Peso de la arista (target, source),
|
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Consulta de combinaciones¶
Columna |
Tipo |
Valores predeterminados |
Descripción |
|---|---|---|---|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
Columnas de Devoluciones¶
Devuelve el conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
seq |
|
Valor secuencial a partir de 1. |
path_id |
|
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 |
path_seq |
|
Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta. |
start_vid |
|
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
end_vid |
|
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
nodo |
|
Identificador del nodo en la ruta de |
arista |
|
Identificador del borde utilizado para ir del |
costo |
|
Costo de desplazamiento desde |
agg_cost |
|
Coste agregado de |
Ejemplos Adicionales¶
Los ejemplos de esta sección se basan en la red Datos Muestra.
Los ejemplos incluyen combinaciones desde los vértices iniciales 2 y 11 hasta los vértices finales 3 y 5 en un grafo dirigido y no dirigido con y sin reverse_cost.
- Ejemplos
Para consultas marcadas como
directedcon columnascostandreverse_cost
Los ejemplos de esta sección utilizan lo siguiente Se utilizan redes para consultas marcadas como directed , cost y reverse_cost
SELECT * FROM pgr_dijkstra(
'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)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 5
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3,5]
);
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 | 5 | 2 | 4 | 1 | 0
8 | 2 | 5 | 5 | -1 | 0 | 1
(8 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
11, 3
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 13 | 1 | 0
2 | 2 | 12 | 15 | 1 | 1
3 | 3 | 9 | 16 | 1 | 2
4 | 4 | 4 | 3 | 1 | 3
5 | 5 | 3 | -1 | 0 | 4
(5 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
11, 5
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 13 | 1 | 0
2 | 2 | 12 | 15 | 1 | 1
3 | 3 | 9 | 9 | 1 | 2
4 | 4 | 6 | 8 | 1 | 3
5 | 5 | 5 | -1 | 0 | 4
(5 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2,11], 5
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | -1 | 0 | 1
3 | 1 | 11 | 11 | 13 | 1 | 0
4 | 2 | 11 | 12 | 15 | 1 | 1
5 | 3 | 11 | 9 | 9 | 1 | 2
6 | 4 | 11 | 6 | 8 | 1 | 3
7 | 5 | 11 | 5 | -1 | 0 | 4
(7 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2, 11], ARRAY[3,5]
);
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 | 2 | 5 | 2 | 4 | 1 | 0
8 | 2 | 2 | 5 | 5 | -1 | 0 | 1
9 | 1 | 11 | 3 | 11 | 13 | 1 | 0
10 | 2 | 11 | 3 | 12 | 15 | 1 | 1
11 | 3 | 11 | 3 | 9 | 16 | 1 | 2
12 | 4 | 11 | 3 | 4 | 3 | 1 | 3
13 | 5 | 11 | 3 | 3 | -1 | 0 | 4
14 | 1 | 11 | 5 | 11 | 13 | 1 | 0
15 | 2 | 11 | 5 | 12 | 15 | 1 | 1
16 | 3 | 11 | 5 | 9 | 9 | 1 | 2
17 | 4 | 11 | 5 | 6 | 8 | 1 | 3
18 | 5 | 11 | 5 | 5 | -1 | 0 | 4
(18 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) AS combinations (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 | 2 | 5 | 2 | 4 | 1 | 0
8 | 2 | 2 | 5 | 5 | -1 | 0 | 1
9 | 1 | 11 | 3 | 11 | 13 | 1 | 0
10 | 2 | 11 | 3 | 12 | 15 | 1 | 1
11 | 3 | 11 | 3 | 9 | 16 | 1 | 2
12 | 4 | 11 | 3 | 4 | 3 | 1 | 3
13 | 5 | 11 | 3 | 3 | -1 | 0 | 4
14 | 1 | 11 | 5 | 11 | 13 | 1 | 0
15 | 2 | 11 | 5 | 12 | 15 | 1 | 1
16 | 3 | 11 | 5 | 9 | 9 | 1 | 2
17 | 4 | 11 | 5 | 6 | 8 | 1 | 3
18 | 5 | 11 | 5 | 5 | -1 | 0 | 4
(18 rows)
- Ejemplos
Para consultas marcadas como
undirectedcon columnascostyreverse_cost
Los ejemplos de esta sección utilizan lo siguiente Se utiliza la red para consultas marcadas como undirected , cost y reverse_cost
SELECT * FROM pgr_dijkstra(
'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)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 5,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
11, 3,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 11 | 1 | 0
2 | 2 | 6 | 5 | 1 | 1
3 | 3 | 3 | -1 | 0 | 2
(3 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
11, 5,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 11 | 1 | 0
2 | 2 | 6 | 8 | 1 | 1
3 | 3 | 5 | -1 | 0 | 2
(3 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2,11], 5,
FALSE
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | -1 | 0 | 1
3 | 1 | 11 | 11 | 12 | 1 | 0
4 | 2 | 11 | 10 | 10 | 1 | 1
5 | 3 | 11 | 5 | -1 | 0 | 2
(5 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3,5],
FALSE
);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 3 | 2 | 2 | 1 | 0
2 | 2 | 3 | 3 | -1 | 0 | 1
3 | 1 | 5 | 2 | 4 | 1 | 0
4 | 2 | 5 | 5 | -1 | 0 | 1
(4 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2, 11], ARRAY[3,5],
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
3 | 1 | 2 | 5 | 2 | 4 | 1 | 0
4 | 2 | 2 | 5 | 5 | -1 | 0 | 1
5 | 1 | 11 | 3 | 11 | 11 | 1 | 0
6 | 2 | 11 | 3 | 6 | 5 | 1 | 1
7 | 3 | 11 | 3 | 3 | -1 | 0 | 2
8 | 1 | 11 | 5 | 11 | 11 | 1 | 0
9 | 2 | 11 | 5 | 6 | 8 | 1 | 1
10 | 3 | 11 | 5 | 5 | -1 | 0 | 2
(10 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) AS combinations (source, target)',
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
3 | 1 | 2 | 5 | 2 | 4 | 1 | 0
4 | 2 | 2 | 5 | 5 | -1 | 0 | 1
5 | 1 | 11 | 3 | 11 | 11 | 1 | 0
6 | 2 | 11 | 3 | 6 | 5 | 1 | 1
7 | 3 | 11 | 3 | 3 | -1 | 0 | 2
8 | 1 | 11 | 5 | 11 | 11 | 1 | 0
9 | 2 | 11 | 5 | 6 | 8 | 1 | 1
10 | 3 | 11 | 5 | 5 | -1 | 0 | 2
(10 rows)
- Ejemplos
Para consultas marcadas como
directedcon columna``cost``
Los ejemplos de esta sección utilizan lo siguiente Red para consultas marcadas como directed y sólo se utiliza la columna cost
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, 3
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, 5
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
11, 3
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
11, 5
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[2,11], 5
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, ARRAY[3,5]
);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 5 | 2 | 4 | 1 | 0
2 | 2 | 5 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[2, 11], ARRAY[3,5]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 5 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) AS combinations (source, target)'
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 5 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | 5 | -1 | 0 | 1
(2 rows)
- Ejemplos
Para consultas marcadas como
undirectedcon columnacost
Los ejemplos de esta sección utilizan lo siguiente Red para consultas marcadas como undirected y solo se utiliza la columna cost
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, 3,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | 8 | 1 | 1
3 | 3 | 6 | 5 | 1 | 2
4 | 4 | 3 | -1 | 0 | 3
(4 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, 5,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
11, 3,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 11 | 1 | 0
2 | 2 | 6 | 5 | 1 | 1
3 | 3 | 3 | -1 | 0 | 2
(3 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
11, 5,
FALSE
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 11 | 11 | 1 | 0
2 | 2 | 6 | 8 | 1 | 1
3 | 3 | 5 | -1 | 0 | 2
(3 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[2,11], 5,
FALSE
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | -1 | 0 | 1
3 | 1 | 11 | 11 | 12 | 1 | 0
4 | 2 | 11 | 10 | 10 | 1 | 1
5 | 3 | 11 | 5 | -1 | 0 | 2
(5 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, ARRAY[3,5],
FALSE
);
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 | 5 | 1 | 2
4 | 4 | 3 | 3 | -1 | 0 | 3
5 | 1 | 5 | 2 | 4 | 1 | 0
6 | 2 | 5 | 5 | -1 | 0 | 1
(6 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[2, 11], ARRAY[3,5],
FALSE
);
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 | 5 | 1 | 2
4 | 4 | 2 | 3 | 3 | -1 | 0 | 3
5 | 1 | 2 | 5 | 2 | 4 | 1 | 0
6 | 2 | 2 | 5 | 5 | -1 | 0 | 1
7 | 1 | 11 | 3 | 11 | 11 | 1 | 0
8 | 2 | 11 | 3 | 6 | 5 | 1 | 1
9 | 3 | 11 | 3 | 3 | -1 | 0 | 2
10 | 1 | 11 | 5 | 11 | 11 | 1 | 0
11 | 2 | 11 | 5 | 6 | 8 | 1 | 1
12 | 3 | 11 | 5 | 5 | -1 | 0 | 2
(12 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) AS combinations (source, target)',
FALSE
);
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 | 5 | 1 | 2
4 | 4 | 2 | 3 | 3 | -1 | 0 | 3
5 | 1 | 2 | 5 | 2 | 4 | 1 | 0
6 | 2 | 2 | 5 | 5 | -1 | 0 | 1
7 | 1 | 11 | 3 | 11 | 11 | 1 | 0
8 | 2 | 11 | 3 | 6 | 5 | 1 | 1
9 | 3 | 11 | 3 | 3 | -1 | 0 | 2
10 | 1 | 11 | 5 | 11 | 11 | 1 | 0
11 | 2 | 11 | 5 | 6 | 8 | 1 | 1
12 | 3 | 11 | 5 | 5 | -1 | 0 | 2
(12 rows)
Equivalencias entre firmas¶
- Ejemplos
Para consultas marcadas como
directedcon columnascostandreverse_cost
Los ejemplos de esta sección utilizan lo siguiente:
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 3,
TRUE
);
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)
SELECT * FROM pgr_dijkstra(
'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)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3],
TRUE
);
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
(6 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3]
);
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
(6 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2], ARRAY[3],
TRUE
);
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
(6 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2], ARRAY[3]
);
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
(6 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM (VALUES(2, 3)) AS combinations (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
(6 rows)
- Ejemplos
Para consultas marcadas como
undirectedcon columnascostyreverse_cost
Los ejemplos de esta sección utilizan lo siguiente:
SELECT * FROM pgr_dijkstra(
'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)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3],
FALSE
);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 3 | 2 | 2 | 1 | 0
2 | 2 | 3 | 3 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2], 3,
FALSE
);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2], ARRAY[3],
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
(2 rows)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM (VALUES(2, 3)) AS combinations (source, target)',
FALSE
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 2 | 1 | 0
2 | 2 | 2 | 3 | 3 | -1 | 0 | 1
(2 rows)
Ver también¶
Las consultas utilizan la red Datos Muestra .
Índices y tablas