• Supported versions:

pgr_KSP

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

Adentro: Boost Graph

Disponibilidad

• 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])

options: [directed, heap_paths]

RETURNS SET OF (seq, path_id, path_seq, 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 | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |    6 |    4 |    1 |        0
   2 |       1 |        2 |    7 |   10 |    1 |        1
   3 |       1 |        3 |    8 |   12 |    1 |        2
   4 |       1 |        4 |   12 |   13 |    1 |        3
   5 |       1 |        5 |   17 |   -1 |    0 |        4
   6 |       2 |        1 |    6 |    4 |    1 |        0
   7 |       2 |        2 |    7 |    8 |    1 |        1
   8 |       2 |        3 |   11 |    9 |    1 |        2
   9 |       2 |        4 |   16 |   15 |    1 |        3
  10 |       2 |        5 |   17 |   -1 |    0 |        4
(10 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 de salida.
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

Columnas de Resultados

Devuelve el 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 primer camnio desde 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 como nodo de salida o nodo destino
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 | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |    6 |    4 |    1 |        0
   2 |       1 |        2 |    7 |   10 |    1 |        1
   3 |       1 |        3 |    8 |   12 |    1 |        2
   4 |       1 |        4 |   12 |   13 |    1 |        3
   5 |       1 |        5 |   17 |   -1 |    0 |        4
   6 |       2 |        1 |    6 |    4 |    1 |        0
   7 |       2 |        2 |    7 |    8 |    1 |        1
   8 |       2 |        3 |   11 |   11 |    1 |        2
   9 |       2 |        4 |   12 |   13 |    1 |        3
  10 |       2 |        5 |   17 |   -1 |    0 |        4
  11 |       3 |        1 |    6 |    4 |    1 |        0
  12 |       3 |        2 |    7 |    8 |    1 |        1
  13 |       3 |        3 |   11 |    9 |    1 |        2
  14 |       3 |        4 |   16 |   15 |    1 |        3
  15 |       3 |        5 |   17 |   -1 |    0 |        4
  16 |       4 |        1 |    6 |    2 |    1 |        0
  17 |       4 |        2 |   10 |    5 |    1 |        1
  18 |       4 |        3 |   11 |    9 |    1 |        2
  19 |       4 |        4 |   16 |   15 |    1 |        3
  20 |       4 |        5 |   17 |   -1 |    0 |        4
(20 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