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

Ambos se pueden utilizar para encontrar el camino más corto desde una sola fuente. BFS entra O(E+V), mientras que Dijkstra corre O((V+E)*log(V)).

Además, he visto que Dijkstra se usa mucho en protocolos de enrutamiento.

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

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

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

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, BFS es la mejor opción.

Por ejemplo, considere los A -> (B, C) -> (F)pesos de los bordes 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 ambos son caminos más cortos (con respecto al número de aristas), pero si aplicamos el de Dijstra, la respuesta será ABF solo porque considera los pesos en el conectado camino.

Algoritmo de Dijkstra

• Como BFS para gráficos ponderados.
• Si todos los costos son iguales, Dijkstra = BFS

Fuente: https://cs.stanford.edu/people/abisee/gs.pdf

Desde la perspectiva de la implementación, el algoritmo de Dijkstra podría implementarse exactamente como un BFS intercambiando el queuecon un priority queue.

Fuente