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.

Boost Graph Inside¶
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.
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
- Example
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 |
x Defecto |
Descripción |
---|---|---|---|
|
Edges SQL as described below. |
Optional parameters¶
Columna |
Tipo |
default |
Descripción |
---|---|---|---|
|
|
|
|
Consulta interna¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
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)
Set of (start_vid, end_vid, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del vértice inicial. |
|
|
Identificador del vértice final. |
|
|
Aggregate cost from |
Ver también¶
Algoritmo floyd-Warshall en Boost
Queries utiliza la red Datos Muestra
Índices y tablas