Versiones anteriores de esta página

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 bidireccional de Dijkstra para crear una matriz de costes de las rutas más cortas.

Sinopsis¶

Basado en el algoritmo de Dijkstra, la búsqueda bidireccional encuentra el camino más corto entre el vértice de inicio al vértice final.

Corre dos búsquedas simultaneas: una adelante de la fuente y otra atrás del objetivo, parándose cuando los dos coinciden en medio.

Esta implementación se puede usar para los grafos dirigidos y no dirigidos.

Las características principales son:

El proceso se realiza sólo en aristas con costos positivos.
- Valor no negativo en una columna de costo se interpreta como la arista no exite.
Los valores se devuelven cuando hay una ruta.
Cuando no hay ruta:
- Cuando el vértice de salida y el vértice destino son iguales.
  - El costo agregado de los valores no incluídos \((v, v)\) es \(0\)
- Cuando el vértice de salida y el vértice destino son diferentes y no hay ninguna ruta:
  - El costo agregado de los valores no incluídos \((u, v)\) es :math: infty
Para fines de optimización, se ignora cualquier valor duplicado en los vertices de salida o destino.
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

Índices y tablas