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.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Version 2.2.0
    • Cambio de firma
    • Firma antigua ya no soportada
  • Versión 2.0.0
    • Función oficial

Soporte

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.
  • Devuelve 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 las aristas con costos positivos.
  • Boost devuelve una matriz:math:V times V donde los valores son infinitos. Representar la distancia entre vértices para los que no hay ruta.
    • Solo devolvemos los valores no infinitos en forma de un conjunto de (start_vid, end_vid, agg_cost).
  • Sea el caso, 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).
  • En caso de 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(edges_sql [, directed])
RETURNS SET OF (start_vid, end_vid,  agg_cost)
OR EMPTY SET

Uso de valores predeterminados

pgr_floydWarshall(edges_sql)
RETURNS SET OF (start_vid, end_vid,  agg_cost)
OR EMPTY SET
Ejemplo 1:Para vértices \(\{1, 2, 3, 4\}\) en un grafo dirigido 
SELECT * FROM pgr_floydWarshall(
    'SELECT id, source, target, cost FROM edge_table where id < 5'
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       5 |        2
         2 |       5 |        1
(3 rows)

Firma completa

pgr_floydWarshall(edges_sql [, directed])
RETURNS SET OF (start_vid, end_vid,  agg_cost)
OR EMPTY SET
Ejemplo 2:Para vértices \(\{1, 2, 3, 4\}\) en un grafo no dirigido 
SELECT * FROM pgr_floydWarshall(
    'SELECT id, source, target, cost FROM edge_table where id < 5',
    false
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       5 |        2
         2 |       1 |        1
         2 |       5 |        1
         5 |       1 |        2
         5 |       2 |        1
(6 rows)

Parámetros

Parámetro Tipo Descripción
edges_sql TEXT Consulta SQL como se describió anteriormente.
dirigido BOOLEAN (opcional) El valor predeterminado es verdadero (es Dirigido). Cuando se establece en falso, el grafo se considera como No Dirigido

Consulta interna

Descripción de la consulta edges_sql (no es necesarioun id)

edges_sql:Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:
Columna Tipo Valores predeterminados Descripción
origen ANY-INTEGER   Identificador del primer punto final en el vértice de la arista.
objetivo ANY-INTEGER   Identificador del segundo punto final en el vértice de la arista.
cost ANY-NUMERICAL  

Peso de la arista (source, target)

  • Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost ANY-NUMERICAL -1

Peso de la arista (target, source),

  • En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve un conjunto de (start_vid, end_vid, agg_cost)

Columna Tipo Descripción
start_vid BIGINT Identificador del vértice inicial.
end_vid BIGINT Identificador del vértice final.
agg_cost FLOAT Costo total de start_vid a end_vid.

Ver también

Índices y tablas