pgr_KSP

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

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

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.

  • New overload functions:

    • 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

Identificador del vértice de salida.

destino

ENTEROS

Identificador del vértice destino.

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

Identificador de la arista.

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

Identificador del vértice de salida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

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

Identificador del camino.

  • 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.

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:

Get 2 paths using combinations table on an undirected graph

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:

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.

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