pgr_KSP

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

_images/boost-inside.jpeg

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

Get 2 paths from \(6\) to \(17\) on a directed graph.

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 Aristas

TEXT

Consulta SQL como se describe.

vid de salida

ENTEROS

Identificador del vértice de salida.

vid 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:

Get 2 paths from \(6\) to \(17\) on an undirected graph

Also get the paths in the heap.

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

Índices y tablas