Versiones soportadas: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Versiones no soportadas:2.6 2.5 2.4 2.3 2.2 2.1 2.0

pgr_KSP

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

Disponibilidad

• Versión 4.0.0

  • Todas las firmas promovidas a oficial.

Versión 3.6.0

• Estandarización de columnas de resultados 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_vid y end_vid.

• Nuevas firmas propuestas:

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

Adentro: Boost Graph

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
SQL de aristas	TEXT	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
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	Cuando false Regresa a lo más K caminos. 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 partida.
target	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
seq	INTEGER	Valor secuencial a partir de 1.
path_id	INTEGER	Identificador del camino. Tiene valor 1 para el primero de la ruta de start_vid a end_vid
path_seq	INTEGER	Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.
node	BIGINT	Identificador del nodo en la ruta de start_vid a 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:

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

• Rutas más cortas K - Categoría

• Datos Muestra

• https://en.wikipedia.org/wiki/K_shortest_path_routing

Índices y tablas

• Índice

• Página de Búsqueda