pgr_ksp - K caminos más cortos¶

Nombre¶

pgr_ksp — Devuelve K caminos más cortos.

Sinopsis¶

El algoritmo del camino más corto K, está basado en el algoritmo de Yen. “K” es el número de caminos más cortos deseados. Regresa un conjunto de registros pgr_costResult3 (seq, id1, id2, id3, cost) que conforman K caminos.

pgr_costResult3[] pgr_ksp(sql text, source integer, target integer,
                         paths integer, has_rcost boolean);

Descripción¶

sql:

Consulta SQL, que debe proporcionar un conjunto de registros con los siguientes campos:

SELECT id, source, target, cost, [,reverse_cost] FROM edge_table

id:	`int4` identificador del borde
source:	`int4` Identificador del vértice inicial de este borde
target:	`int4` Identificador del vértice final del borde
cost:	`float8` valor del costo del recorrido sobre el borde. Un costo negativo evitará que el borde sea insertado en el gráfico.
reverse_cost:	(opcional) el costo para el recorrido inverso del borde. Se utiliza sólo cuando el parámetro `has_rcost` es `True` (ver el comentario anterior acerca de los costos negativos).

source:

int4 Identificador del punto de partida

target:

int4 Identificador del punto de llegada

paths:

int4 Cantidad de rutas alternativas

has_rcost:

Si es True, el campo reverse_cost del conjunto de registros generados se utilizan para el calcular el costo de la travesía del borde en la dirección opuesta.

Arroja un conjunto del tipo de datos pgr_costResult[]:

seq:	secuencia para ordenar los resultados
id1:	Identificador de la ruta
id2:	Identificador del nodo visitado
id3:	Identificador del borde ( `0` para el ultimo registro)
cost:	costo para atravesar desde el nodo `id2` usando el borde `id3` hasta su otro extremo

El código base de KSP fue adquirido de http://code.google.com/p/k-shortest-paths/source.

Historia

Nuevo en la versión 2.0.0

Ejemplos¶

Sin reverse_cost

SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
 FROM pgr_ksp(
   'SELECT id, source, target, cost FROM edge_table',
   7, 12, 2, false
 );

 seq | route | node | edge | cost
-----+-------+------+------+------
   0 |     0 |    7 |    6 |    1
   1 |     0 |    8 |    7 |    1
   2 |     0 |    5 |    8 |    1
   3 |     0 |    6 |   11 |    1
   4 |     0 |   11 |   13 |    1
   5 |     0 |   12 |    0 |    0
   6 |     1 |    7 |    6 |    1
   7 |     1 |    8 |    7 |    1
   8 |     1 |    5 |    8 |    1
   9 |     1 |    6 |    9 |    1
  10 |     1 |    9 |   15 |    1
  11 |     1 |   12 |    0 |    0
(12 rows)

Con reverse_cost

SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
 FROM pgr_ksp(
   'SELECT id, source, target, cost, reverse_cost FROM edge_table',
   7, 12, 2, true
 );

 seq | route | node | edge | cost
-----+-------+------+------+------
   0 |     0 |    7 |    6 |    1
   1 |     0 |    8 |    7 |    1
   2 |     0 |    5 |    8 |    1
   3 |     0 |    6 |   11 |    1
   4 |     0 |   11 |   13 |    1
   5 |     0 |   12 |    0 |    0
   6 |     1 |    7 |    6 |    1
   7 |     1 |    8 |    7 |    1
   8 |     1 |    5 |    8 |    1
   9 |     1 |    6 |    9 |    1
  10 |     1 |    9 |   15 |    1
  11 |     1 |   12 |    0 |    0
(12 rows)

Las consultas usan la red de ejemplo Datos Muestra

pgRouting Manual (2.0.0)