pgRouting Manual (2.0.0)

pgr_apspWarshall - Camino más corto de todos los pares, Algoritmo de Floyd-Warshall

«  pgr_apspJohnson - Ruta más corta de todos los pares, algoritmo de Johnson   ::   Contents   ::   pgr_astar - Camino más corto A*  »


pgr_apspWarshall - Camino más corto de todos los pares, Algoritmo de Floyd-Warshall

Nombre

pgr_apspWarshall - Devuelve todos los costos de cada par de nodos en la gráfica.

Sinopsis

El algoritmo de Floyd-Warshall (también conocido como algoritmo de Floyd y otros nombres) es un algoritmo de análisis gráfico para encontrar los caminos más cortos entre todos los pares de nodos en un gráfico ponderado. Devuelve un conjunto de registros (seq, id1, id2, cost) pgr_costResult para cada par de nodos en el gráfico.

pgr_costResult[] pgr_apspWarshall(sql text, directed boolean, reverse_cost boolean);

Descripción

sql:

una consulta SQL quedebe proporcionar los bordes de la gráfica que va a ser analizada:

SELECT source, target, 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 un valor positivo para el costo de atravesar este borde
directed:

true Si la gráfica es direccionada

reverse_cost:

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 de partida
id2:Identificador del nodo de llegada
cost:costo para viajar desde el nodo id1 hasta el nodo id2

Historia

  • Nuevo en la versión 2.0.0

Ejemplos

SELECT seq, id1 AS from, id2 AS to, cost
    FROM pgr_apspWarshall(
        'SELECT id, source, target, cost FROM edge_table',
        false, false
    );

 seq | from | to | cost
-----+------+----+------
   0 |    1 |  1 |    0
   1 |    1 |  2 |    1
   2 |    1 |  3 |    0
   3 |    1 |  4 |   -1
[...]

La consulta usa la red del ejemplo Datos Muestra

«  pgr_apspJohnson - Ruta más corta de todos los pares, algoritmo de Johnson   ::   Contents   ::   pgr_astar - Camino más corto A*  »