pgr_KSP — Devuelve la ruta más corta «K».
Adentro: Boost Graph
Disponibilidad
Soporte
El algoritmo de ruteo para obtener la ruta más corta K basado en el algoritmo de Yen . «K» es el número de rutas más cortas deseadas.
Resumen
pgr_KSP(edges_sql, start_vid, end_vid, K [, directed] [, heap_paths])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
Uso de valores predeterminados
pgr_ksp(edges_sql, start_vid, end_vid, K);
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
| Ejemplo: | TBD |
|---|
pgr_KSP(edges_sql, start_vid, end_vid, K [, directed] [, heap_paths])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
| Ejemplo: | TBD |
|---|
| Columna | Tipo | Descripción |
|---|---|---|
| edges_sql | TEXT |
Consulta SQL como se describió anteriormente. |
| start_vid | BIGINT |
Identificador del vértice inicial. |
| end_vid | BIGINT |
Identificador del vértice final. |
| k | INTEGER |
El número de rutas desedadas. |
| dirigido | BOOLEAN |
(opcional). En caso de false el grafo se considera como No Dirigido. El valor predeterminado es true que considera el grafo como Dirigido. |
| heap_paths | BOOLEAN |
(opcional). En caso de true se devuelven todas las rutas almacenadas en el montón de procesos. El valor predeterminado es false que solo devuelve rutas k. |
Aproximadamente, si la ruta más corta tiene N aristas, el montón contendrá aproximadamente más que las rutas N * k para valores pequeños de k y k > 1.
| 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. | |
| cost | ANY-NUMERICAL |
Peso de la arista (source, target)
|
|
| reverse_cost | ANY-NUMERICAL |
-1 | Peso de la arista (target, source),
|
Donde:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Ddevuelve el conjunto de (seq, path_seq, path_id, node, edge, cost, agg_cost)
| Columna | Tipo | Descripción |
|---|---|---|
| seq | INTEGER |
Valor secuencial a partir de 1. |
| path_seq | INTEGER |
Posición relativa en la ruta de node y edge. El valor es 1 para el inicio de una ruta. |
| path_id | BIGINT |
Identificador de rutas. El orden de las rutas para dos rutas i, j if i < j entonces agg_cost(i) <= agg_cost(j). |
| node | BIGINT |
Identificador del nodo en la ruta. |
| edge | BIGINT |
Identificador de la arista utilizada para ir desde node al siguiente nodo en la secuencia de ruta . -1 para el último nodo de la ruta. |
| cost | FLOAT |
Costo de desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta. |
| agg_cost | FLOAT |
Costo agregado de start_vid a node. |
| Ejemplo: | Para manejar la única marca para elegir firmas |
|---|
Los ejemplos de esta sección utilizan lo siguiente Se utilizan redes para consultas marcadas como directed , cost y reverse_cost
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2,
directed:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
| Ejemplo: | Para consultas marcadas como directed con columnas cost and reverse_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_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
(15 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, true, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
(15 rows)
| Ejemplos: | Para consultas marcadas como undirected con columnas cost y reverse_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_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, directed:=false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 2 | 1 | 0
2 | 1 | 2 | 3 | 3 | 1 | 1
3 | 1 | 3 | 4 | 16 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 10 | 1 | 1
8 | 2 | 3 | 10 | 12 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, false, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 2 | 1 | 0
2 | 1 | 2 | 3 | 3 | 1 | 1
3 | 1 | 3 | 4 | 16 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
16 | 4 | 1 | 2 | 4 | 1 | 0
17 | 4 | 2 | 5 | 10 | 1 | 1
18 | 4 | 3 | 10 | 12 | 1 | 2
19 | 4 | 4 | 11 | 11 | 1 | 3
20 | 4 | 5 | 6 | 9 | 1 | 4
21 | 4 | 6 | 9 | 15 | 1 | 5
22 | 4 | 7 | 12 | -1 | 0 | 6
(22 rows)
| Ejemplo: | Para consultas marcadas como directed con 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_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 3, 2
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
(0 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
(15 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, true, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
(15 rows)
| Ejemplo: | Para consultas marcadas como undirected con columna cost |
|---|
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_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, directed:=false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
(10 rows)
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, directed:=false, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 2 | 4 | 1 | 0
2 | 1 | 2 | 5 | 8 | 1 | 1
3 | 1 | 3 | 6 | 9 | 1 | 2
4 | 1 | 4 | 9 | 15 | 1 | 3
5 | 1 | 5 | 12 | -1 | 0 | 4
6 | 2 | 1 | 2 | 4 | 1 | 0
7 | 2 | 2 | 5 | 8 | 1 | 1
8 | 2 | 3 | 6 | 11 | 1 | 2
9 | 2 | 4 | 11 | 13 | 1 | 3
10 | 2 | 5 | 12 | -1 | 0 | 4
11 | 3 | 1 | 2 | 4 | 1 | 0
12 | 3 | 2 | 5 | 10 | 1 | 1
13 | 3 | 3 | 10 | 12 | 1 | 2
14 | 3 | 4 | 11 | 13 | 1 | 3
15 | 3 | 5 | 12 | -1 | 0 | 4
(15 rows)
Índices y tablas