Por que usar o algoritmo de Dijkstra se o BFS (Breadth First Search) pode fazer a mesma coisa mais rápido?

Ambos podem ser usados ​​para encontrar o caminho mais curto de uma fonte única. O BFS entra O(E+V), enquanto o de Dijkstra entra O((V+E)*log(V)).

Além disso, vi Dijkstra ser usado de maneira muito semelhante aos protocolos de roteamento.

Portanto, por que usar o algoritmo de Dijkstra se o BFS pode fazer a mesma coisa mais rápido?

Dijkstra permite atribuir distâncias diferentes de 1 para cada etapa. Por exemplo, no roteamento, as distâncias (ou pesos) podem ser atribuídos por velocidade, custo, preferência, etc. O algoritmo então fornece o caminho mais curto de sua origem a cada nó no gráfico percorrido.

Enquanto isso, o BFS basicamente expande a pesquisa em uma "etapa" (link, borda, como você quiser chamá-la em sua aplicação) em cada iteração, o que tem o efeito de encontrar o menor número de etapas necessárias para chegar a qualquer determinado nó de sua fonte (“raiz”).

Se você considerar sites de viagens, eles usam o algoritmo de Dijkstra por causa dos pesos (distâncias) dos nós.

Se você considerar a mesma distância entre todos os nós, então o BFS é a melhor escolha.

Por exemplo, considere os A -> (B, C) -> (F)pesos das arestas dados por A->B= 10, A->C= 20, B->F= C->F= 5.

Aqui, se aplicarmos BFS, a resposta será ABF ou ACF, pois ambos são caminhos mais curtos (no que diz respeito ao número de arestas), mas se aplicarmos Dijstra, a resposta será ABF apenas porque considera os pesos nos caminho.

Algoritmo de Dijkstra

• Como o BFS para gráficos ponderados.
• Se todos os custos forem iguais, Dijkstra = BFS

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

Do ponto de vista da implementação, o algoritmo de Dijkstra poderia ser implementado exatamente como um BFS trocando o queuepor a priority queue.

Fonte