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

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?

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»).

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.

Algorithme de Dijkstra

• Comme BFS pour les graphiques pondérés.
• Si tous les coûts sont égaux, Dijkstra = BFS

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

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