Dijkstra - Familia de funciones

propuesta

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.

Versiones anteriores de esta página

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