Versiones soportadas: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Versiones no soportadas:2.6 2.5 2.4 2.3 2.2

Dijkstra - Familia de funciones¶

pgr_dijkstra - Algoritmo de Dijkstra para las rutas más cortas.
pgr_dijkstraCost - Obtenga el costo agrgado de las rutas más cortas.
pgr_dijkstraCostMatrix - Use pgr_dijkstra para crear una matriz de costos.
pgr_drivingDistance - Use pgr_dijkstra para calcular información de captación.
pgr_KSP - Use el algoritmo Yen con pgr_dijkstra para obtener las rutas más cortas K.

Propuesto

Advertencia

Funciones propuestas para el próximo lanzamineto.

No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
- Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL
- Es posible que el nombre no cambie. (Pero todavía puede)
- Es posible que la firma no cambie. (Pero todavía puede)
- Es posible que la funcionalidad no cambie. (Pero todavía puede)
- Se han hecho pruebas de pgTap. Pero tal vez necesite más.
- Es posible que la documentación necesite un refinamiento.

pgr_dijkstraVia - Propuesto - Obtenga una ruta a partir de una secuencia de vértices.

Experimental

Advertencia

Funciones propuestas para el próximo lanzamineto.

No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
- Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL
- Es posible que el nombre no cambie. (Pero todavía puede)
- Es posible que la firma no cambie. (Pero todavía puede)
- Es posible que la funcionalidad no cambie. (Pero todavía puede)
- Se han hecho pruebas de pgTap. Pero tal vez necesite más.
- Es posible que la documentación necesite un refinamiento.

pgr_dijkstraNear - Experimental - Obtener la ruta al vértice más cercano.
pgr_dijkstraNearCost - Experimental - Get the cost to the nearest vertex.

La definición de problema (Documentación avanzada)¶

Dada la siguiente consulta:

pgr_dijkstra( $s q l, s t a r t_{v i d}, e n d_{v i d}, d i r e c t e d$ )

Donde $s q l = {(i d_{i}, s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}, r e v e r s e_c o s t_{i})}$

$s o u r c e = ⋃ s o u r c e_{i}$ ,
$t a r g e t = ⋃ t a r g e t_{i}$ ,

Los gráficos se definen como sigue:

Grafo dirigido

El gráfico dirigido ponderado, $G_{d} (V, E)$ , se define por:

Conjunto de vértices $V$
- $V = s o u r c e \cup t a r g e t \cup s t a r t_{v i d} \cup e n d_{v i d}$
El conjunto de aristas $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

Grafo no dirigido

El grafo ponderado no dirigido $G_{u} (V, E)$ , es definido por:

Conjunto de vértices $V$
- $V = s o u r c e \cup t a r g e t \cup s t a r t_{v} v i d \cup e n d_{v i d}$
El conjunto de aristas $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} \\ \cup {(s o u r c e_{i}, t a r g e t_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

El problema

Dado:

$s t a r t_{v i d} \in V$ a starting vertex
$e n d_{v i d} \in V$ un vértice final
$G (V, E) = {\begin{cases} G_{d} (V, E) & if6 d i r e c t e d = t r u e \\ G_{u} (V, E) & if5 d i r e c t e d = f a l s e \end{cases}$

Entonces:

$π = {(p a t h_s e q_{i}, n o d e_{i}, e d g e_{i}, c o s t_{i}, a g g_c o s t_{i})}$

Donde:

$p a t h_s e q_{i} = i$
$p a t h_s e q_{| π |} = | π |$
$n o d e_{i} \in V$
$n o d e_{1} = s t a r t_{v i d}$
$n o d e_{| π |} = e n d_{v i d}$
$\forall i \neq | π |, (n o d e_{i}, n o d e_{i + 1}, c o s t_{i}) \in E$
$e d g e_{i} = {\begin{cases} i d_{(n o d e_{i}, n o d e_{i + 1}, c o s t_{i})} & when i \neq | π | \\ - 1 & when i = | π | \end{cases}$
$c o s t_{i} = c o s t_{(n o d e_{i}, n o d e_{i + 1})}$
$a g g_c o s t_{i} = {\begin{cases} 0 & when i = 1 \\ \sum_{k = 1}^{i} c o s t_{(n o d e_{k - 1}, n o d e_{k})} & when i \neq 1 \end{cases}$

En otras palabras: El algoritmo devuelve una ruta más corta entre $s t a r t_{v i d}$ y $e n d_{v i d}$ , si es que existe, en términos de una secuencia de nodos y de aristas,

$p a t h_s e q$ indica la posición relativa en el camino de $n o d e$ o $e d g e$ .
$c o s t$ es el coste del borde que se utilizará para ir al siguiente nodo.
$a g g_c o s t$ es el costo desde el $s t a r t_{v i d}$ hasta el nodo.

Si no hay ruta, el conjunto resultante estará vacío.

Ver también¶

Índices y tablas