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

Sinopsis

Based on Dijkstra’s algorithm, the bidirectional search finds a shortest path a starting vertex to an ending vertex.

It runs two simultaneous searches: one forward from the source, and one backward from the target, stopping when the two meet in the middle.

This implementation can be used with a directed graph and an undirected graph.

Características

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

Ver también

Índices y tablas