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 d’une source unique. BFS s’exécute dans O (E + V), tandis que Dijkstra s’exécute dans O ((V + E) * log (V)).

Aussi, j’ai vu Dijkstra beaucoup utilisé dans les protocoles de routage.

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

    Dijkstra permet d’atsortingbuer des distances autres que 1 pour chaque étape. Par exemple, dans le routage, les distances (ou poids) peuvent être atsortingbué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 traversé.

    Pendant ce temps, BFS étend simplement la recherche par une «étape» (lien, bord, tout ce que vous voulez appeler dans votre application) à chaque itération, ce qui a pour effet de trouver le plus petit nombre d’étapes nécessaires nœud donné de votre source (“root”).

    Si vous considérez des 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érons A -> (B, C) -> (F) avec des 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 plus courts (par rapport au nombre d’arêtes), mais si nous appliquons Dijstra, la réponse sera ABF uniquement parce qu’il considère les pondérations sur les connexions. chemin.