pgr_KSP¶
pgr_KSP — Devuelve las K rutas más cortas usando Dijkstra .
Adentro: Boost Graph¶
Disponibilidad
Versión 3.6.0
Columnas de resultados estandarizadas a:
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)pgr_ksp(Uno a Uno)Añadidas las columnas de resultados
start_vidyend_vid.
Nuevas funciones de sobrecarga:
pgr_ksp(Uno a muchos)pgr_ksp(Muchos a uno)pgr_ksp(Muchos a muchos)pgr_ksp(Combinaciones)
Versión 2.1.0
Cambio de firma
Firma antigua ya no soportada
Versión 2.0.0
Función oficial
Descripción¶
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.
Firmas¶
Resumen
pgr_KSP(SQL de aristas, salida, destino, K, [opciones])
pgr_KSP(SQL de aristas, salida, destinos, K, [opciones])
pgr_KSP(SQL de aristas, salidas, destino, K, [opciones])
pgr_KSP(SQL de aristas, salidas, destinos, K, [opciones])
pgr_KSP(SQL de aristas, SQL de combinaciones, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
Uno a Uno¶
pgr_KSP(SQL de aristas, salida, destino, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
- Ejemplo:
Obteners 2 caminos desde \(6\) hasta \(17\) en un grafo dirigido.
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 17 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 17 | 7 | 10 | 1 | 1
3 | 1 | 3 | 6 | 17 | 8 | 12 | 1 | 2
4 | 1 | 4 | 6 | 17 | 12 | 13 | 1 | 3
5 | 1 | 5 | 6 | 17 | 17 | -1 | 0 | 4
6 | 2 | 1 | 6 | 17 | 6 | 4 | 1 | 0
7 | 2 | 2 | 6 | 17 | 7 | 8 | 1 | 1
8 | 2 | 3 | 6 | 17 | 11 | 9 | 1 | 2
9 | 2 | 4 | 6 | 17 | 16 | 15 | 1 | 3
10 | 2 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(10 rows)
Uno a Muchos¶
pgr_KSP(SQL de aristas, salida, destinos, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
- Ejemplo:
Obtener 2 rutas del vértice \(6\) a los vértices \(\{10, 17\}\) en un grafo dirigido.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17], 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 1 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 1 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 1 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 1 | 6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 2 | 1 | 6 | 10 | 6 | 4 | 1 | 0
8 | 2 | 2 | 6 | 10 | 7 | 10 | 1 | 1
9 | 2 | 3 | 6 | 10 | 8 | 12 | 1 | 2
10 | 2 | 4 | 6 | 10 | 12 | 13 | 1 | 3
11 | 2 | 5 | 6 | 10 | 17 | 15 | 1 | 4
12 | 2 | 6 | 6 | 10 | 16 | 16 | 1 | 5
13 | 2 | 7 | 6 | 10 | 15 | 3 | 1 | 6
14 | 2 | 8 | 6 | 10 | 10 | -1 | 0 | 7
15 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
16 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
17 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
18 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
19 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
20 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
21 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
22 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
23 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
24 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(24 rows)
Muchos a Uno¶
pgr_KSP(SQL de aristas, salidas, destino, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
- Ejemplo:
Obtener 2 rutas de los vértices \(\{6, 1\}\) al vértice \(17\) en un grafo dirigido.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 17 | 7 | 10 | 1 | 2
4 | 1 | 4 | 1 | 17 | 8 | 12 | 1 | 3
5 | 1 | 5 | 1 | 17 | 12 | 13 | 1 | 4
6 | 1 | 6 | 1 | 17 | 17 | -1 | 0 | 5
7 | 2 | 1 | 1 | 17 | 1 | 6 | 1 | 0
8 | 2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
9 | 2 | 3 | 1 | 17 | 7 | 8 | 1 | 2
10 | 2 | 4 | 1 | 17 | 11 | 9 | 1 | 3
11 | 2 | 5 | 1 | 17 | 16 | 15 | 1 | 4
12 | 2 | 6 | 1 | 17 | 17 | -1 | 0 | 5
13 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
14 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
15 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
16 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
17 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
18 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
19 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
20 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
21 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
22 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(22 rows)
Muchos a Muchos¶
pgr_KSP(SQL de aristas, salidas, destinos, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
- Ejemplo:
Obtener 2 rutas los vértices \(\{6, 1\}\) a los vértices \(\{10, 17\}\) en un grafo dirigido.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 10 | 7 | 8 | 1 | 2
4 | 1 | 4 | 1 | 10 | 11 | 9 | 1 | 3
5 | 1 | 5 | 1 | 10 | 16 | 16 | 1 | 4
6 | 1 | 6 | 1 | 10 | 15 | 3 | 1 | 5
7 | 1 | 7 | 1 | 10 | 10 | -1 | 0 | 6
8 | 2 | 1 | 1 | 10 | 1 | 6 | 1 | 0
9 | 2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
10 | 2 | 3 | 1 | 10 | 7 | 10 | 1 | 2
11 | 2 | 4 | 1 | 10 | 8 | 12 | 1 | 3
12 | 2 | 5 | 1 | 10 | 12 | 13 | 1 | 4
13 | 2 | 6 | 1 | 10 | 17 | 15 | 1 | 5
14 | 2 | 7 | 1 | 10 | 16 | 16 | 1 | 6
15 | 2 | 8 | 1 | 10 | 15 | 3 | 1 | 7
16 | 2 | 9 | 1 | 10 | 10 | -1 | 0 | 8
17 | 3 | 1 | 1 | 17 | 1 | 6 | 1 | 0
18 | 3 | 2 | 1 | 17 | 3 | 7 | 1 | 1
19 | 3 | 3 | 1 | 17 | 7 | 10 | 1 | 2
20 | 3 | 4 | 1 | 17 | 8 | 12 | 1 | 3
21 | 3 | 5 | 1 | 17 | 12 | 13 | 1 | 4
22 | 3 | 6 | 1 | 17 | 17 | -1 | 0 | 5
23 | 4 | 1 | 1 | 17 | 1 | 6 | 1 | 0
24 | 4 | 2 | 1 | 17 | 3 | 7 | 1 | 1
25 | 4 | 3 | 1 | 17 | 7 | 8 | 1 | 2
26 | 4 | 4 | 1 | 17 | 11 | 9 | 1 | 3
27 | 4 | 5 | 1 | 17 | 16 | 15 | 1 | 4
28 | 4 | 6 | 1 | 17 | 17 | -1 | 0 | 5
29 | 5 | 1 | 6 | 10 | 6 | 4 | 1 | 0
30 | 5 | 2 | 6 | 10 | 7 | 8 | 1 | 1
31 | 5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
32 | 5 | 4 | 6 | 10 | 16 | 16 | 1 | 3
33 | 5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
34 | 5 | 6 | 6 | 10 | 10 | -1 | 0 | 5
35 | 6 | 1 | 6 | 10 | 6 | 4 | 1 | 0
36 | 6 | 2 | 6 | 10 | 7 | 10 | 1 | 1
37 | 6 | 3 | 6 | 10 | 8 | 12 | 1 | 2
38 | 6 | 4 | 6 | 10 | 12 | 13 | 1 | 3
39 | 6 | 5 | 6 | 10 | 17 | 15 | 1 | 4
40 | 6 | 6 | 6 | 10 | 16 | 16 | 1 | 5
41 | 6 | 7 | 6 | 10 | 15 | 3 | 1 | 6
42 | 6 | 8 | 6 | 10 | 10 | -1 | 0 | 7
43 | 7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
44 | 7 | 2 | 6 | 17 | 7 | 10 | 1 | 1
45 | 7 | 3 | 6 | 17 | 8 | 12 | 1 | 2
46 | 7 | 4 | 6 | 17 | 12 | 13 | 1 | 3
47 | 7 | 5 | 6 | 17 | 17 | -1 | 0 | 4
48 | 8 | 1 | 6 | 17 | 6 | 4 | 1 | 0
49 | 8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
50 | 8 | 3 | 6 | 17 | 11 | 9 | 1 | 2
51 | 8 | 4 | 6 | 17 | 16 | 15 | 1 | 3
52 | 8 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(52 rows)
Combinaciones¶
pgr_KSP(SQL de aristas, SQL de combinaciones, K, [opciones])
opcionales:
[directed, heap_paths]Regresa conjunto de
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)O CONJUNTO VACÍO
- Ejemplo:
Usando una tabla de combinaciones en un grafo dirigido
La tabla de combinaciones:
SELECT source, target FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
La consulta:
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 2 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 2 | 5 | 10 | 6 | 4 | 1 | 1
5 | 2 | 3 | 5 | 10 | 7 | 8 | 1 | 2
6 | 2 | 4 | 5 | 10 | 11 | 9 | 1 | 3
7 | 2 | 5 | 5 | 10 | 16 | 16 | 1 | 4
8 | 2 | 6 | 5 | 10 | 15 | 3 | 1 | 5
9 | 2 | 7 | 5 | 10 | 10 | -1 | 0 | 6
10 | 3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
11 | 3 | 2 | 5 | 10 | 6 | 4 | 1 | 1
12 | 3 | 3 | 5 | 10 | 7 | 10 | 1 | 2
13 | 3 | 4 | 5 | 10 | 8 | 12 | 1 | 3
14 | 3 | 5 | 5 | 10 | 12 | 13 | 1 | 4
15 | 3 | 6 | 5 | 10 | 17 | 15 | 1 | 5
16 | 3 | 7 | 5 | 10 | 16 | 16 | 1 | 6
17 | 3 | 8 | 5 | 10 | 15 | 3 | 1 | 7
18 | 3 | 9 | 5 | 10 | 10 | -1 | 0 | 8
19 | 4 | 1 | 6 | 5 | 6 | 1 | 1 | 0
20 | 4 | 2 | 6 | 5 | 5 | -1 | 0 | 1
21 | 5 | 1 | 6 | 15 | 6 | 4 | 1 | 0
22 | 5 | 2 | 6 | 15 | 7 | 8 | 1 | 1
23 | 5 | 3 | 6 | 15 | 11 | 9 | 1 | 2
24 | 5 | 4 | 6 | 15 | 16 | 16 | 1 | 3
25 | 5 | 5 | 6 | 15 | 15 | -1 | 0 | 4
26 | 6 | 1 | 6 | 15 | 6 | 4 | 1 | 0
27 | 6 | 2 | 6 | 15 | 7 | 10 | 1 | 1
28 | 6 | 3 | 6 | 15 | 8 | 12 | 1 | 2
29 | 6 | 4 | 6 | 15 | 12 | 13 | 1 | 3
30 | 6 | 5 | 6 | 15 | 17 | 15 | 1 | 4
31 | 6 | 6 | 6 | 15 | 16 | 16 | 1 | 5
32 | 6 | 7 | 6 | 15 | 15 | -1 | 0 | 6
(32 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
Consulta SQL como se describe. |
|
salida |
ENTEROS |
Identificador del vértice de partida. |
destino |
ENTEROS |
Identificador del vértice destino. |
K |
ENTEROS |
Cantidad de rutas requeridas. |
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
Parámetros opcionales de KSP¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
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 partida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT
Columnas de resultados¶
Regresa conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde
|
|
|
Costo agregado desde vid inicial hasta |
Ejemplos Adicionales¶
- Ejemplo:
Obteners 2 caminos desde \(6\) hasta \(17\) en un grafo no dirigido
También obtener los caminos procesados.
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2,
directed => false, heap_paths => true
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 17 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 17 | 7 | 10 | 1 | 1
3 | 1 | 3 | 6 | 17 | 8 | 12 | 1 | 2
4 | 1 | 4 | 6 | 17 | 12 | 13 | 1 | 3
5 | 1 | 5 | 6 | 17 | 17 | -1 | 0 | 4
6 | 2 | 1 | 6 | 17 | 6 | 4 | 1 | 0
7 | 2 | 2 | 6 | 17 | 7 | 8 | 1 | 1
8 | 2 | 3 | 6 | 17 | 11 | 11 | 1 | 2
9 | 2 | 4 | 6 | 17 | 12 | 13 | 1 | 3
10 | 2 | 5 | 6 | 17 | 17 | -1 | 0 | 4
11 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
12 | 3 | 2 | 6 | 17 | 7 | 8 | 1 | 1
13 | 3 | 3 | 6 | 17 | 11 | 9 | 1 | 2
14 | 3 | 4 | 6 | 17 | 16 | 15 | 1 | 3
15 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
16 | 4 | 1 | 6 | 17 | 6 | 2 | 1 | 0
17 | 4 | 2 | 6 | 17 | 10 | 5 | 1 | 1
18 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
19 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
20 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(20 rows)
- Ejemplo:
Obtener dos rutas usando una tabla de combinaciones en un grafo no dirigido
También obtener los caminos procesados.
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2, directed => false, heap_paths => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 2 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 2 | 5 | 10 | 6 | 2 | 1 | 1
5 | 2 | 3 | 5 | 10 | 10 | -1 | 0 | 2
6 | 3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
7 | 3 | 2 | 5 | 10 | 6 | 4 | 1 | 1
8 | 3 | 3 | 5 | 10 | 7 | 8 | 1 | 2
9 | 3 | 4 | 5 | 10 | 11 | 5 | 1 | 3
10 | 3 | 5 | 5 | 10 | 10 | -1 | 0 | 4
11 | 4 | 1 | 6 | 5 | 6 | 1 | 1 | 0
12 | 4 | 2 | 6 | 5 | 5 | -1 | 0 | 1
13 | 5 | 1 | 6 | 15 | 6 | 2 | 1 | 0
14 | 5 | 2 | 6 | 15 | 10 | 3 | 1 | 1
15 | 5 | 3 | 6 | 15 | 15 | -1 | 0 | 2
16 | 6 | 1 | 6 | 15 | 6 | 4 | 1 | 0
17 | 6 | 2 | 6 | 15 | 7 | 8 | 1 | 1
18 | 6 | 3 | 6 | 15 | 11 | 9 | 1 | 2
19 | 6 | 4 | 6 | 15 | 16 | 16 | 1 | 3
20 | 6 | 5 | 6 | 15 | 15 | -1 | 0 | 4
21 | 7 | 1 | 6 | 15 | 6 | 2 | 1 | 0
22 | 7 | 2 | 6 | 15 | 10 | 5 | 1 | 1
23 | 7 | 3 | 6 | 15 | 11 | 9 | 1 | 2
24 | 7 | 4 | 6 | 15 | 16 | 16 | 1 | 3
25 | 7 | 5 | 6 | 15 | 15 | -1 | 0 | 4
(25 rows)
- Ejemplo:
Obtener 2 rutas de los vértices \(\{6, 1\}\) al vértice \(17\) en un grafo no dirigido.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2, directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 17 | 7 | 10 | 1 | 2
4 | 1 | 4 | 1 | 17 | 8 | 12 | 1 | 3
5 | 1 | 5 | 1 | 17 | 12 | 13 | 1 | 4
6 | 1 | 6 | 1 | 17 | 17 | -1 | 0 | 5
7 | 2 | 1 | 1 | 17 | 1 | 6 | 1 | 0
8 | 2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
9 | 2 | 3 | 1 | 17 | 7 | 8 | 1 | 2
10 | 2 | 4 | 1 | 17 | 11 | 9 | 1 | 3
11 | 2 | 5 | 1 | 17 | 16 | 15 | 1 | 4
12 | 2 | 6 | 1 | 17 | 17 | -1 | 0 | 5
13 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
14 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
15 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
16 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
17 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
18 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
19 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
20 | 4 | 3 | 6 | 17 | 11 | 11 | 1 | 2
21 | 4 | 4 | 6 | 17 | 12 | 13 | 1 | 3
22 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(22 rows)
- Ejemplo:
Obtener 2 rutas los vértices \(\{6, 1\}\) a los vértices \(\{10, 17\}\) en un grafo dirigido.
También obtener los caminos procesados.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2, heap_paths => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 10 | 7 | 8 | 1 | 2
4 | 1 | 4 | 1 | 10 | 11 | 9 | 1 | 3
5 | 1 | 5 | 1 | 10 | 16 | 16 | 1 | 4
6 | 1 | 6 | 1 | 10 | 15 | 3 | 1 | 5
7 | 1 | 7 | 1 | 10 | 10 | -1 | 0 | 6
8 | 2 | 1 | 1 | 10 | 1 | 6 | 1 | 0
9 | 2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
10 | 2 | 3 | 1 | 10 | 7 | 10 | 1 | 2
11 | 2 | 4 | 1 | 10 | 8 | 12 | 1 | 3
12 | 2 | 5 | 1 | 10 | 12 | 13 | 1 | 4
13 | 2 | 6 | 1 | 10 | 17 | 15 | 1 | 5
14 | 2 | 7 | 1 | 10 | 16 | 16 | 1 | 6
15 | 2 | 8 | 1 | 10 | 15 | 3 | 1 | 7
16 | 2 | 9 | 1 | 10 | 10 | -1 | 0 | 8
17 | 3 | 1 | 1 | 10 | 1 | 6 | 1 | 0
18 | 3 | 2 | 1 | 10 | 3 | 7 | 1 | 1
19 | 3 | 3 | 1 | 10 | 7 | 8 | 1 | 2
20 | 3 | 4 | 1 | 10 | 11 | 11 | 1 | 3
21 | 3 | 5 | 1 | 10 | 12 | 13 | 1 | 4
22 | 3 | 6 | 1 | 10 | 17 | 15 | 1 | 5
23 | 3 | 7 | 1 | 10 | 16 | 16 | 1 | 6
24 | 3 | 8 | 1 | 10 | 15 | 3 | 1 | 7
25 | 3 | 9 | 1 | 10 | 10 | -1 | 0 | 8
26 | 4 | 1 | 1 | 17 | 1 | 6 | 1 | 0
27 | 4 | 2 | 1 | 17 | 3 | 7 | 1 | 1
28 | 4 | 3 | 1 | 17 | 7 | 10 | 1 | 2
29 | 4 | 4 | 1 | 17 | 8 | 12 | 1 | 3
30 | 4 | 5 | 1 | 17 | 12 | 13 | 1 | 4
31 | 4 | 6 | 1 | 17 | 17 | -1 | 0 | 5
32 | 5 | 1 | 1 | 17 | 1 | 6 | 1 | 0
33 | 5 | 2 | 1 | 17 | 3 | 7 | 1 | 1
34 | 5 | 3 | 1 | 17 | 7 | 8 | 1 | 2
35 | 5 | 4 | 1 | 17 | 11 | 11 | 1 | 3
36 | 5 | 5 | 1 | 17 | 12 | 13 | 1 | 4
37 | 5 | 6 | 1 | 17 | 17 | -1 | 0 | 5
38 | 6 | 1 | 1 | 17 | 1 | 6 | 1 | 0
39 | 6 | 2 | 1 | 17 | 3 | 7 | 1 | 1
40 | 6 | 3 | 1 | 17 | 7 | 8 | 1 | 2
41 | 6 | 4 | 1 | 17 | 11 | 9 | 1 | 3
42 | 6 | 5 | 1 | 17 | 16 | 15 | 1 | 4
43 | 6 | 6 | 1 | 17 | 17 | -1 | 0 | 5
44 | 7 | 1 | 6 | 10 | 6 | 4 | 1 | 0
45 | 7 | 2 | 6 | 10 | 7 | 8 | 1 | 1
46 | 7 | 3 | 6 | 10 | 11 | 9 | 1 | 2
47 | 7 | 4 | 6 | 10 | 16 | 16 | 1 | 3
48 | 7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
49 | 7 | 6 | 6 | 10 | 10 | -1 | 0 | 5
50 | 8 | 1 | 6 | 10 | 6 | 4 | 1 | 0
51 | 8 | 2 | 6 | 10 | 7 | 10 | 1 | 1
52 | 8 | 3 | 6 | 10 | 8 | 12 | 1 | 2
53 | 8 | 4 | 6 | 10 | 12 | 13 | 1 | 3
54 | 8 | 5 | 6 | 10 | 17 | 15 | 1 | 4
55 | 8 | 6 | 6 | 10 | 16 | 16 | 1 | 5
56 | 8 | 7 | 6 | 10 | 15 | 3 | 1 | 6
57 | 8 | 8 | 6 | 10 | 10 | -1 | 0 | 7
58 | 9 | 1 | 6 | 10 | 6 | 4 | 1 | 0
59 | 9 | 2 | 6 | 10 | 7 | 8 | 1 | 1
60 | 9 | 3 | 6 | 10 | 11 | 11 | 1 | 2
61 | 9 | 4 | 6 | 10 | 12 | 13 | 1 | 3
62 | 9 | 5 | 6 | 10 | 17 | 15 | 1 | 4
63 | 9 | 6 | 6 | 10 | 16 | 16 | 1 | 5
64 | 9 | 7 | 6 | 10 | 15 | 3 | 1 | 6
65 | 9 | 8 | 6 | 10 | 10 | -1 | 0 | 7
66 | 10 | 1 | 6 | 17 | 6 | 4 | 1 | 0
67 | 10 | 2 | 6 | 17 | 7 | 10 | 1 | 1
68 | 10 | 3 | 6 | 17 | 8 | 12 | 1 | 2
69 | 10 | 4 | 6 | 17 | 12 | 13 | 1 | 3
70 | 10 | 5 | 6 | 17 | 17 | -1 | 0 | 4
71 | 11 | 1 | 6 | 17 | 6 | 4 | 1 | 0
72 | 11 | 2 | 6 | 17 | 7 | 8 | 1 | 1
73 | 11 | 3 | 6 | 17 | 11 | 11 | 1 | 2
74 | 11 | 4 | 6 | 17 | 12 | 13 | 1 | 3
75 | 11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
76 | 12 | 1 | 6 | 17 | 6 | 4 | 1 | 0
77 | 12 | 2 | 6 | 17 | 7 | 8 | 1 | 1
78 | 12 | 3 | 6 | 17 | 11 | 9 | 1 | 2
79 | 12 | 4 | 6 | 17 | 16 | 15 | 1 | 3
80 | 12 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(80 rows)
Ver también¶
Índices y tablas