Supported versions:

pgr_johnson¶

pgr_johnson - Devuelve la suma de los costes de la ruta más corta para cada par de nodos del 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

Descripción¶

El algoritmo Johnson, 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 dispersos. Utiliza la implementación del Boost que se ejecuta en \(O(V E \log V)\) 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.

Firmas¶

Resumen

pgr_johnson(edges_sql)
pgr johnson(edges_sql [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Uso de valores predeterminados

pgr_johnson(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_johnson(
    'SELECT source, target, cost FROM edge_table WHERE id < 5
         ORDER BY id'
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       5 |        2
         2 |       5 |        1
(3 rows)

Firma completa¶

pgr_johnson(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_johnson(
    'SELECT source, target, cost FROM edge_table WHERE id < 5
         ORDER BY id',
    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¶

pgr_floydWarshall
Boost Johnson algorithm implementation.
Queries utiliza la red Datos Muestra

Índices y tablas