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
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
