pgr_floydWarshall

pgr_floydWarshall - Devuelve la suma de los costos de la ruta más corta para cada par de nodos en el grafo mediante el algoritmo Floyd-Warshall.

Adentro: Boost Graph

Disponibilidad

• Version 2.2.0

  • Cambio de firma

  • Firma antigua ya no soportada

• Versión 2.0.0

  • Función oficial

Descripción

El algoritmo Floyd-Warshall, también conocido como algoritmo de Floyd, es una buena opción para calcular la suma de los costos de la ruta más corta para cada par de nodos en el grafo, para grafos densos. Usamos la implementación de Boost que se ejecuta en \(\Theta(V^3)\) tiempo,

Las principales características son:

• No devuelve una ruta.

• Regresa la suma de los costos de la ruta más corta para cada par de nodos del grafo.

• El proceso se realiza sólo en aristas con costos positivos.

• Boost devuelve una matriz \(V \times V\) donde los valores infinitos representan la distancia entre vértices para los que no hay ruta.

  • Solo regresa los valores no infinitos en forma de un conjunto de (start_vid, end_vid, agg_cost).

• Sea el caso donde los valores devueltos se almacenan en una tabla, por lo que el índice único sería el par: (start_vid, end_vid).

• Para el grafo no dirigido, los resultados son simétricos.

  • El agg_cost de (u, v) es el mismo que para (v, u).

• Cuando start_vid = end_vid, el agg_cost = 0.

• Recomendación: utilice un cuadro delimitador de no más de 3500 aristas.

Firmas

Resumen

pgr_floydWarshall(SQL de aristas, [directed])

Regresa el conjunto de (start_vid, end_vid, agg_cost)

O CONJUNTO VACÍO

Ejemplo:

Para sub-grafo con aristas \(\{1, 2, 3, 4\}\).

SELECT * FROM pgr_floydWarshall(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges where id < 5'
) ORDER BY start_vid, end_vid;
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |       7 |        2
         6 |       5 |        1
         6 |       7 |        1
         7 |       5 |        2
         7 |       6 |        1
        10 |       5 |        2
        10 |       6 |        1
        10 |       7 |        2
        15 |       5 |        3
        15 |       6 |        2
        15 |       7 |        3
        15 |      10 |        1
(13 rows)

Parámetros

Parámetro	Tipo	x Defecto	Descripción
SQL de aristas	TEXT		SQL de aristas descritas más adelante.

Parámetros opcionales

Columna	Tipo	x Defecto	Descripción
directed	BOOLEAN	true	Cuando true el gráfo se considera Dirigido Cuando false el gráfo se considera No Dirigido.

Consultas Internas

SQL aristas

Columna	Tipo	x Defecto	Descripción
source	ENTEROS		Identificador del primer vértice de la arista.
target	ENTEROS		Identificador del segundo vértice de la arista.
cost	FLOTANTES		Peso de la arista (source, target)
reverse_cost	FLOTANTES	-1	Peso de la arista (target, source) Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

Conjunto de (start_vid, end_vid, agg_cost)

Columna	Tipo	Descripción
start_vid	BIGINT	Identificador del vértice de salida.
end_vid	BIGINT	Identificador del vértice final.
agg_cost	FLOAT	Costo afregado desde start_vid hasta end_vid.

Ver también

• pgr_johnson

• Boost Algoritmo floyd-Warshall

• Consultas utilizan la red Datos Muestra.

Índices y tablas

• Índice

• Página de Búsqueda