Dijkstra - Familia de funciones¶

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

• Índice
• Página de Búsqueda