pgr_kDijkstra - Camino más corto camino con múltiples destinos de Dijkstra¶

Nombre¶

pgr_kdijkstraCost - Devuelve los costos de K caminos más cortos usando el algoritmo de Dijkstra.
pgr_kdijkstraPath - Devuelve los K caminos más cortos usando el algoritmo de Dijkstra.

Sinopsis¶

Estas funciones permiten calcular las rutas a todos los destinos desde un nodo de partida único hasta múltiples nodos de destino. Devuelve un conjunto de pgr_costResult o de pgr_costResult3. pgr_kdijkstraCost devuelve un registro para cada nodo destino y el costo total de la ruta hasta ese nodo. pgr_kdijkstraPath devuelve un registro por cada borde en la ruta desde la fuente hasta el destino junto con el costo para atravesar ese borde.

pgr_costResult[] pgr_kdijkstraCost(text sql, integer source,
                 integer[] targets, boolean directed, boolean has_rcost);

pgr_costResult3[] pgr_kdijkstraPath(text sql, integer source,
                  integer[] targets, boolean directed, boolean has_rcost);

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 del 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. Esto sólo se utiliza cuando los parámetros `directed` y `has_rcost` son `True` (ver el comentario anterior sobre los costos negativos).

source:

int4 Identificador del punto de partida

targets:

int4[] Una matriz de identificadores de los puntos de llegada

directed:

true Si la gráfica es direccionada

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.

pgr_kdijkstraCost devuelve el conjunto de pgr_costResult[]:

seq:	Secuencia de registros
id1:	Identificador del vértice de llegada (esto siempre será punto de partida en la consulta).
id2:	Identificador del vértice de llegada.
cost:	Costo para recorrer el camino desde `id1` hasta `id2`. Costo será -1.0 si no hay camino al identificador de vértice de destino.

pgr_kdijkstraPath devuelve el conjunto de pgr_costResult3[] - resultados múltiples de recorridos con costo:

seq:	Secuencia de registros
id1:	Identificador de “este borde” de la ruta (hacia el destino).
id2:	id del nodo de partida en “este borde”
id3:	id de “este borde” (`-1` para la última fila)
cost:	Costo para atravesar este borde o -1.0 si no hay ningún camino

Historia

Nuevo en la versión 2.0.0

Ejemplos¶

Devolviendo un resultado de costos cost

SELECT seq, id1 AS source, id2 AS target, cost FROM pgr_kdijkstraCost(
    'SELECT id, source, target, cost FROM edge_table',
    10, array[4,12], false, false
);

 seq | source | target | cost
-----+--------+--------+------
   0 |     10 |      4 |    4
   1 |     10 |     12 |    2

SELECT seq, id1 AS path, id2 AS node, id3 AS edge, cost
  FROM pgr_kdijkstraPath(
      'SELECT id, source, target, cost FROM edge_table',
      10, array[4,12], false, false
);

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

Devolviendo resultado de un trayecto path

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
  FROM pgr_kdijkstraPath(
                  'SELECT id, source, target, cost FROM edge_table',
                  10, array[4,12], false, false
            ) a,
            edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1;

path |            the_geom
------+---------------------------------
    4 | LINESTRING(2 3,3 3,4 3,4 2,4 1)
   12 | LINESTRING(2 3,3 3,4 3)
(2 rows)

No hay ninguna garantía de que el resultado anterior esté ordenado en la dirección del flujo de la ruta, es decir, puede estar invertido. Usted necesitará comprobar si st_startPoint() de la ruta es la misma que la ubicación del nodo de inicio y si no, entonces utilizar st_reverse() para invertir la dirección de la ruta. Este comportamiento es de funciones pertenecientes a PostGIS st_linemerge() y st_union() y no pertenecen a pgRouting.

pgRouting Manual (2.0.0)