pgr_dijkstraCost

pgr_dijkstraCost - Total cost of the shortest path(s) using Dijkstra algorithm.

_images/boost-inside.jpeg

Boost Graph Inside

Disponibilidad

  • Versión 3.1.0

  • Version 2.2.0

    • Nueva función Oficial

Descripción

The pgr_dijkstraCost function sumarizes of the cost of the shortest path(s) using Dijkstra Algorithm.

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.

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

    • A negative value on a cost column is interpreted as the edge does not exist.

  • Valores son regresados cuando hay una ruta.

  • When there is no path:

    • When the starting vertex and ending vertex are the same.

      • The aggregate cost of the non included values \((v, v)\) is \(0\)

    • When the starting vertex and ending vertex are the different and there is no path:

      • The aggregate cost the non included values \((u, v)\) is \(\infty\)

  • For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

  • Running time: \(O(| start\ vids | * (V \log V + E))\)

  • No devuelve una ruta.

  • Returns the sum of the costs of the shortest path of each pair combination of nodes requested.

  • Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid).

  • Depending on the function and its parameters, the results can be symmetric.

    • The aggregate cost of \((u, v)\) is the same as for \((v, u)\).

  • Any duplicated value in the start or end vertex identifiers are ignored.

  • Los valores regresados se ordenan:

    • start_vid ascending

    • end_vid ascending

Firmas

Resumen

pgr_dijkstraCost(Edges SQL, start vid, end vid  [, directed])
pgr_dijkstraCost(Edges SQL, start vid, end vids [, directed])
pgr_dijkstraCost(Edges SQL, start vids, end vid  [, directed])
pgr_dijkstraCost(Edges SQL, start vids, end vids [, directed])
pgr_dijkstraCost(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Uno a Uno

pgr_dijkstraCost(Edges SQL, start vid, end vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

Del vértice \(2\) al vértice \(3\) en un grafo dirigido

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  2, 3, true);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
(1 row)

Uno a Muchos

pgr_dijkstraCost(Edges SQL, start vid, end vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

From vertex \(2\) to vertices \(\{3, 12\}\) on a directed graph

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  2, ARRAY[3, 12]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      12 |        4
(2 rows)

Muchos a Uno

pgr_dijkstraCost(Edges SQL, start vids, end vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

From vertices \(\{2, 7\}\) to vertex \(12\) on a directed graph

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  ARRAY[2, 7], 12);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |      12 |        4
         7 |      12 |        5
(2 rows)

Muchos a Muchos

pgr_dijkstraCost(Edges SQL, start vids, end vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

From vertices \(\{2, 7\}\) to vertices \(\{3, 12\}\) on an undirected graph

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  ARRAY[2, 7], ARRAY[3, 12],
  directed => false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        1
         2 |      12 |        4
         7 |       3 |        4
         7 |      12 |        5
(4 rows)

Combinaciones

pgr_dijkstraCost(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Ejemplo

Uso de una tabla de combinaciones en un grafo no direccionado

The combinations table:

SELECT source, target FROM combinations_table;
 source | target
--------+--------
      1 |      2
      1 |      3
      2 |      1
      2 |      4
      2 |     17
(5 rows)

The query:

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  'SELECT source, target FROM combinations_table',
  false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       3 |        2
         2 |       1 |        1
         2 |       4 |        2
(4 rows)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below

Combinations SQL

TEXT

Combinations SQL as described below

start vid

BIGINT

Identificador del vértice inicial de la ruta.

start vids

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

end vid

BIGINT

Identificador del vértice final de la ruta.

end vids

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Optional parameters

Columna

Tipo

default

Descripción

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • Cuando false el gráfo se considera No Dirigido.

Inner queries

Edges SQL

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Parámetro

Tipo

Descripción

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Columnas de Devoluciones

Set of (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

Coste agregado de start_vid a end_vid.

Ejemplos Adicionales

Ejemplo 1

La demostración de valores repetidos se omite y el resultado se ordena.

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  ARRAY[5, 3, 4, 3, 3, 4], ARRAY[3, 5, 3, 4]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         3 |       4 |        3
         3 |       5 |        2
         4 |       3 |        1
         4 |       5 |        3
         5 |       3 |        4
         5 |       4 |        3
(6 rows)

Ejemplo 2

Making start_vids the same as end_vids.

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  ARRAY[5, 3, 4], ARRAY[5, 3, 4]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         3 |       4 |        3
         3 |       5 |        2
         4 |       3 |        1
         4 |       5 |        3
         5 |       3 |        4
         5 |       4 |        3
(6 rows)

Ejemplo 3

Manually assigned vertex combinations.

SELECT * FROM pgr_dijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edge_table',
  'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3)) AS combinations (source, target)');
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |       5 |        1
        11 |       3 |        4
(3 rows)

Ver también

Índices y tablas