Pourquoi utiliser l'algorithme de Dijkstra si la recherche en largeur (BFS) peut faire la même chose plus rapidement ?

Question

Les deux peuvent être utilisés pour trouver le chemin le plus court à partir d'une source unique. BFS fonctionne en O(E+V) tandis que les parcours de Dijkstra en 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 ?

Answer 1

Dijkstra permet d'attribuer des distances différentes de 1 pour chaque étape. Par exemple, dans le routage, les distances (ou poids) peuvent être attribuées en fonction de la vitesse, du coût, de la préférence, etc. L'algorithme vous donne ensuite le chemin le plus court entre votre source et chaque nœud du graphe traversé.

Pendant ce temps, la BFS ne fait qu'étendre la recherche d'un "pas" (lien, bord, peu importe comment vous voulez l'appeler dans votre application) à chaque itération, ce qui a pour effet de trouver le plus petit nombre d'étapes qu'il faut pour atteindre un nœud donné à partir de votre source ("Root").

Answer 2

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 A -> (B, C) -> (F) avec des poids d'arêtes 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 des chemins les plus courts (par rapport au nombre d'arêtes), mais si nous appliquons la méthode de Dijstra, la réponse sera ABF uniquement parce qu'elle tient compte des poids sur le chemin connecté.

Answer 3

Algorithme de Dijkstra

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

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

Answer 4

Du point de vue de la mise en œuvre, l'algorithme de Dijkstra pourrait être mis en œuvre exactement comme un BFS en intervertissant l'élément queue avec un priority queue .

Source :

Answer 5

Il y a une confusion à ce sujet, il est possible d'utiliser l'algorithme BFS modifié pour trouver le plus court chemin dans un graphe dirigé pondéré :

1. Utiliser une file d'attente prioritaire au lieu d'une file d'attente normale
2. Ne pas suivre les nœuds visités, mais plutôt la distance depuis le nœud de départ.

À cause de 2, certains nœuds seront visités plus d'une fois, ce qui le rend moins efficace que Dijkstra.

shortest = sys.maxsize

queue = [(0, src, 0)]
while queue:
    (cost, node, hops) = heapq.heappop(queue)
    if node == dst:
        shortest = min(distance, cheapest)
    for (node_to, node_distance) in edges[node]:
        heapq.heappush(queue, (cost + node_distance, node_to, hops + 1))