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(\(sql, start_{vid}, end_{vid}, directed\))
Donde \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
y
\(source = \bigcup source_i\),
\(target = \bigcup target_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 = source \cup target \cup {start_{vid}} \cup {end_{vid}}\)
El conjunto de aristas \(E\)
\(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \quad \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i>=0 \} & \quad \text{if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Grafo no dirigido
El grafo ponderado no dirigido \(G_u(V,E)\), es definido por:
Conjunto de vértices \(V\)
\(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)
El conjunto de aristas \(E\)
\(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \text{ } \\ \cup \{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
El problema
Dado:
\(start_{vid} \in V\) a starting vertex
\(end_{vid} \in V\) un vértice final
\(G(V,E) = \begin{cases} G_d(V,E) & \quad \text{ if6 } directed = true \\ G_u(V,E) & \quad \text{ if5 } directed = false \\ \end{cases}\)
Entonces:
\(\boldsymbol{\pi} = \{(path\_seq_i, node_i, edge_i, cost_i, agg\_cost_i)\}\)
- Donde:
\(path\_seq_i = i\)
\(path\_seq_{| \pi |} = | \pi |\)
\(node_i \in V\)
\(node_1 = start_{vid}\)
\(node_{| \pi |} = end_{vid}\)
\(\forall i \neq | \pi |, \quad (node_i, node_{i+1}, cost_i) \in E\)
\(edge_i = \begin{cases} id_{(node_i, node_{i+1},cost_i)} &\quad \text{when } i \neq | \pi | \\ -1 &\quad \text{when } i = | \pi | \\ \end{cases}\)
\(cost_i = cost_{(node_i, node_{i+1})}\)
\(agg\_cost_i = \begin{cases} 0 &\quad \text{when } i = 1 \\ \displaystyle\sum_{k=1}^{i} cost_{(node_{k-1}, node_k)} &\quad \text{when } i \neq 1 \\ \end{cases}\)
- En otras palabras: El algoritmo devuelve una ruta más corta entre \(start_{vid}\) y \(end_{vid}\), si es que existe, en términos de una secuencia de nodos y de aristas,
\(path\_seq\) indica la posición relativa en el camino de \(node\) o \(edge\).
\(cost\) es el coste del borde que se utilizará para ir al siguiente nodo.
\(agg\_cost\) es el costo desde el \(start_{vid}\) hasta el nodo.
Si no hay ruta, el conjunto resultante estará vacío.
Ver también¶
Índices y tablas