pgr_dijkstra - Camino más corto de Dijkstra¶

Nombre¶

pgr_dijkstra — Devuelve el Camino más corto usando el algoritmo de Dijkstra

Sinopsis¶

El algoritmo de Dijkstra, fue concebido por el científico computacional holandés, Edsger Dijkstra en 1956. Se trata de un algoritmo de búsqueda gráfica que resuelve el problema del camino más corto de una sola fuente con costos no negativos, generando un árbol de ruta más corta. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, cost) que conforman un recorrido.

pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
                           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:	`float8` (opcional) el costo para el recorrido inverso del borde. Sólo se usa cuando los parámetros de `directed` y `has_rcost` son `true` (véase el comentario anterior sobre costos negativos).

source:

int4 identificador del punto de partida

target:

int4 Identificador del punto de llegada

directed:

true Si la gráfica es direccional

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.

Devuelve un conjunto del tipo de datos pgr_costResult[]:

seq:	Secuencia de registros
id1:	Identificador del nodo visitado
id2:	Identificador del borde (`-1` para el último borde)
cost:	costo para atravesar desde el nodo `id1` usando el borde `id2` hasta el otro extremo del borde

Historia

Renombrado en la versión 2.0.0

Ejemplos¶

Sin reverse_cost

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

 seq | node | edge | cost
-----+------+------+------
   0 |    7 |    8 |    1
   1 |    8 |    9 |    1
   2 |    9 |   15 |    1
   3 |   12 |   -1 |    0
(4 rows)

Con reverse_cost

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

 seq | node | edge | cost
-----+------+------+------
   0 |    7 |    8 |    1
   1 |    8 |    9 |    1
   2 |    9 |   15 |    1
   3 |   12 |   -1 |    0
(4 rows)

Las consultas usan la red de ejemplo Datos Muestra

pgRouting Manual (2.0.0)