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

pgRouting Manual (2.0.0)