# pgr_KSP¶

pgr_KSP — Devuelve las K rutas más cortas usando Dijkstra .

Version 3.6.0

• Return columns standarized to: (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

• pgr_ksp (One to One)

• Added start_vid and end_vid result columns.

• pgr_ksp (One to Many)

• pgr_ksp (Many to One)

• pgr_ksp (Many to Many)

• pgr_ksp (Combinations)

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(Edges SQL, start vid, end vids, K, [options])
pgr_KSP(Edges SQL, start vids, end vid, K, [options])
pgr_KSP(Edges SQL, start vids, end vids, K, [options])
pgr_KSP(Edges SQL, Combinations SQL, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

### Uno a Uno¶

pgr_KSP(SQL de aristas, salida, destino, K, [opciones])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
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(Edges SQL, start vid, end vids, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Get 2 paths from vertex $$6$$ to vertices $$\{10, 17\}$$ on a directed graph.

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(Edges SQL, start vids, end vid, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Get 2 paths from vertices $$\{6, 1\}$$ to vertex $$17$$ on a directed graph.

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(Edges SQL, start vids, end vids, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Get 2 paths vertices $$\{6, 1\}$$ to vertices $$\{10, 17\}$$ on a directed graph.

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(Edges SQL, Combinations SQL, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Using a combinations table on an directed graph

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

SQL de aristas

TEXT

Consulta SQL como se describe.

salida

ENTEROS

destino

ENTEROS

K

ENTEROS

Number of required paths.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

### Parámetros opcionales¶

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

• Cuando true el gráfo se considera Dirigido

• Cuando false el gráfo se considera No Dirigido.

## Parámetros opcionales de KSP¶

Columna

Tipo

x Defecto

Descripción

heap_paths

BOOLEAN

false

• When false Returns at most K paths.

• Cuando true se regresan todos los caminos calulados mientras se procesa.

• Aproximadamente, si la ruta más corta tiene N aristas, las procesadas contendrán aproximadamente N * K rutas para valores pequeños de K y K > 5.

## Consultas Internas¶

### SQL aristas¶

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

• Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

### SQL Combinaciones¶

Parámetro

Tipo

Descripción

source

ENTEROS

target

ENTEROS

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Returns set of (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

• Has value 1 for the first of a path from start_vid to end_vid

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.

node

BIGINT

Identifier of the node in the path from start_vid to end_vid

edge

BIGINT

Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.

cost

FLOAT

Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta.

• $$0$$ para el último node de la ruta.

agg_cost

FLOAT

Costo agregado desde vid inicial hasta node.

Ejemplo:

Obteners 2 caminos desde $$6$$ hasta $$17$$ en un grafo no dirigido

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:

Get 2 paths using combinations table on an undirected graph

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:

Get 2 paths from vertices $$\{6, 1\}$$ to vertex $$17$$ on a undirected graph.

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:

Get 2 paths vertices $$\{6, 1\}$$ to vertices $$\{10, 17\}$$ on a directed graph.

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)



Índices y tablas