algorithm - profundidad - ¿Por qué usar el algoritmo de Dijkstra si Breadth First Search(BFS) puede hacer lo mismo más rápido?

busqueda en profundidad c++

Question

Ambos pueden usarse para encontrar la ruta más corta desde una única fuente. BFS se ejecuta en O (E + V), mientras que Dijkstra se ejecuta en O ((V + E) * log (V)).

Además, he visto a Dijkstra usar mucho como en los protocolos de enrutamiento.

Por lo tanto, ¿por qué usar el algoritmo de Dijkstra si BFS puede hacer lo mismo más rápido?

Answer 1

Dijkstra permite asignar distancias distintas de 1 para cada paso. Por ejemplo, en el enrutamiento, las distancias (o pesos) se pueden asignar por velocidad, costo, preferencia, etc. El algoritmo luego le proporciona la ruta más corta desde su origen hasta cada nodo en el gráfico atravesado.

Mientras tanto, BFS simplemente expande la búsqueda en un "paso" (enlace, borde, como quiera llamarlo en su aplicación) en cada iteración, que tiene el efecto de encontrar el menor número de pasos necesarios para llegar a cualquier nodo dado de su fuente ("raíz").

Answer 2

Si considera los sitios web de viajes, estos utilizan el algoritmo de Dijkstra debido a los pesos (distancias) en los nodos.

Si considera la misma distancia entre todos los nodos, entonces BFS es la mejor opción.

Por ejemplo, considere A -> (B, C) -> (F) con los pesos de borde dados por A->B = 10, A->C = 20, B->F = C->F = 5.

Aquí, si aplicamos BFS, la respuesta será ABF o ACF, ya que ambas son las trayectorias más cortas (con respecto al número de aristas), pero si aplicamos las de Dijstra, la respuesta será ABF solo porque considera los pesos en la conexión camino.