Pourquoi utiliser l'algorithme de Dijkstra si Breadth First Search (BFS) peut faire la même chose plus rapidement?

110

Les deux peuvent être utilisés pour trouver le chemin le plus court à partir d'une seule source. BFS entre O(E+V), tandis que Dijkstra court O((V+E)*log(V)).

De plus, j'ai vu Dijkstra beaucoup utilisé comme dans les protocoles de routage.

Ainsi, pourquoi utiliser l'algorithme de Dijkstra si BFS peut faire la même chose plus rapidement?

chat roux
la source

Réponses:

156

Dijkstra permet d'attribuer des distances autres que 1 pour chaque étape. Par exemple, dans le routage, les distances (ou poids) pourraient être attribuées par vitesse, coût, préférence, etc. L'algorithme vous donne alors le chemin le plus court de votre source à chaque nœud du graphe parcouru.

Pendant ce temps, BFS étend simplement la recherche d'une «étape» (lien, bord, comme vous voulez l'appeler dans votre application) à chaque itération, ce qui a pour effet de trouver le plus petit nombre d'étapes nécessaires pour atteindre un nœud donné de votre source («racine»).

Arkku
la source
1
Les deux donneront les mêmes résultats, c'est-à-dire un chemin entre deux sommets, mais seul dijkstra garantira le chemin le plus court.
Edwin
Voir la réponse acceptée, deuxième commentaire. Très belle façon d'expliquer pourquoi la complexité de calcul est différente: stackoverflow.com/questions/25449781
...
24

Si vous considérez les sites Web de voyage, ceux-ci utilisent l'algorithme de Dijkstra en raison des poids (distances) sur les nœuds.

Si vous considérez la même distance entre tous les nœuds, alors BFS est le meilleur choix.

Par exemple, considérez les A -> (B, C) -> (F)poids de bord donnés par A->B= 10, A->C= 20, B->F= C->F= 5.

Ici, si nous appliquons BFS, la réponse sera ABF ou ACF, car les deux sont les chemins les plus courts (en ce qui concerne le nombre d'arêtes), mais si nous appliquons Dijstra, la réponse sera ABF uniquement parce qu'il considère les poids sur le connecté chemin.

Saurabh Saluja
la source
4

Du point de vue de la mise en œuvre, l'algorithme de Dijkstra pourrait être implémenté exactement comme un BFS en échangeant le queueavec un priority queue.

La source

Havij
la source