Bidirectional Dijkstra - Familia de funciones

  • pgr_bdDijkstra - Algoritmo Dijkstra bidireccional para las rutas más cortas.
  • pgr_bdDijkstraCost - Dijkstra bidireccional para calcular el costo de las rutas más cortas
  • pgr_bdDijkstraCostMatrix - Algoritmo Dijkstra bidireccional para crear una matriz de costos de las rutas más cortas.

Versiones anteriores de esta página

  • Versiones soportadas: actual(3.1) 3.0 2.6
  • Versiones no soportadas: 2.5

Sinopsis

Basada en el algoritmo Dijkstra, la búsqueda bidireccional encuentra una ruta más corta: de un vértice inicial (start_vid) a un vértice final (end_vid). Ejecuta dos búsquedas simultáneas: una adelante de la fuente y uno hacia atrás del objetivo, deteniéndose cuando los dos se encuentran en el medio. Esta implementación puede utilizarse con un gráfico dirigido y uno no dirigido.

Características

Las características principales son:

  • El proceso se realiza sólo en las aristas con costos positivos.
  • Valores son regresados cuando hay un camino.
  • Cuando el vértice inicial y el vértice final son iguales, no hay camino.
    • El agg_cost de los valores no incluídos (v, v) es 0
  • Cuando el vértice inicial y el vértice final son diferentes y no hay camino:
    • El “agg_cost” de los valores no incluídos “(u, v)” es :math: infty
  • Tiempo de ejecución (peor de los casos): \(O((V \log V + E))\)
  • Para grandes gráficos donde hay un camino entre el vértice inicial y el vértice final:
    • Se espera que termine más rápido que pgr_dijkstra

Ver también

Índices y tablas