pgRouting Manual (2.0.0)

pgr_bdDijkstra - Camino más corto bidireccional de Dijkstra

«  pgr_bdAstar - Camino más corto bidireccional A*   ::   Contents   ::   pgr_dijkstra - Camino más corto de Dijkstra  »


pgr_bdDijkstra - Camino más corto bidireccional de Dijkstra

Nombre

pgr_bdDijkstra - Devuelve el recorrido más corto bidireccional usando el algoritmo de Dijkstra

Sinopsis

Este es un algoritmo de búsqueda bidireccional de Dijkstra. Realiza una búsqueda desde la fuente hacia el destino y, al mismo tiempo, desde el destino hacia el origen, terminando donde estas búsquedas se reúnen en el centro. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, cost) que conforman un camino.

pgr_costResult[] pgr_bdDijkstra(sql text, source integer, target integer,
                                directed boolean, 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 de este 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

target:

int4 Identificador del punto 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 utiliza 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)
cost:costo del recorrido desde el nodo id1 usando el borde id2 hasta el otro extremo del borde

Historia

  • Nuevo en la versión 2.0.0

Ejemplos

  • Sin reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost FROM edge_table',
        4, 10, false, false
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    0
       1 |    3 |    5 |    1
       2 |    6 |   11 |    1
       3 |   11 |   12 |    0
       4 |   10 |   -1 |    0
    (5 rows)
  • Con reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        4, 10, true, true
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    1
       1 |    3 |    2 |    1
       2 |    2 |    4 |    1
       3 |    5 |   10 |    1
       4 |   10 |   -1 |    0
    (5 rows)

Las consultas usan la red de ejemplo Datos Muestra

«  pgr_bdAstar - Camino más corto bidireccional A*   ::   Contents   ::   pgr_dijkstra - Camino más corto de Dijkstra  »