Bellman-Ford vs Dijkstra: dans quelles circonstances Bellman-Ford est-elle meilleure?
après beaucoup de recherches sur Google, j'ai trouvé que la plupart des sources disent que L'algorithme de Dijkstra est "plus efficace" que L'algorithme de Bellman-Ford. Mais dans quelles circonstances L'algorithme de Bellman-Ford est-il meilleur que L'algorithme de Dijkstra?
je sais que "mieux" est un énoncé général, donc spécifiquement je veux dire en termes de vitesse et aussi d'espace si cela s'applique. Il y a certainement des situations où L'approche Bellman-Ford est meilleure que L'approche Dijkstra.
5 réponses
l'algorithme Bellman-Ford est un algorithme de chemin le plus court, donc quand vous avez un poids de bord négatif, il peut détecter des cycles négatifs dans un graphique.
la seule différence entre les deux est que Bellman Ford est capable de gérer des poids négatifs alors que Dijkstra algorithme ne peut gérer positifs.
cependant, L'algorithme de Dijkstra sélectionne avec avidité le noeud de poids minimum qui n'a pas encore été traitées, et exécute ce processus de relaxation sur tous ses bords sortants; en revanche, L'algorithme Bellman–Ford détends simplement tous les bords, et fait ceci | V / - 1 fois, où |V | est le nombre de sommets dans le graphe. Dans chacune de ces répétitions, le nombre de Sommets avec des distances calculées correctement croît, de qu'il s'ensuit que finalement tous les sommets auront leurs corrects distance. cette méthode permet d'appliquer L'algorithme Bellman–Ford pour un classe d'entrées plus large que Dijkstra.
Dijkstra est cependant généralement considéré comme meilleur en l'absence de bordures de poids négatives, comme une mise en file d'attente de priorité binaire typique de tas A O (((E|+|V|)log|V|) complexité de temps [une file D'attente de priorité de tas de Fibonacci donne O (|V|log| V | + | E/)], tandis que L'algorithme de Bellman-Ford a o (|V|| E/) complexité
la seule différence est que L'algorithme de Dijkstra ne peut pas gérer les poids de bord négatifs que Bellman-ford manipule.Et bellman-ford nous dit aussi si le graphique contient le cycle négatif. Si graph ne contient pas des bords négatifs, alors Dijkstra est toujours mieux.
une alternative efficace pour Bellman-ford est le graphe acyclique dirigé (DAG) qui utilise des tri.
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
comme déjà indiqué dans la réponse choisie, Bellman-Ford effectue la vérification sur tous les sommets, Dijkstra seulement sur celui avec la meilleure distance calculée à ce jour. Encore une fois déjà noté, cela améliore la complexité de L'approche de Dijkstra, mais il faut comparer tous les noeuds pour trouver la valeur de la distance minimale. Cela n'étant pas nécessaire dans le Bellman-Ford, il est plus facile à mettre en œuvre dans un environnement distribué. C'est pourquoi il est utilisé dans les protocoles de routage vectoriel à Distance (par ex., RIP et IGRP), où l'on utilise surtout des informations locales. Pour utiliser Dijkstra dans les protocoles de routage, il faut d'abord distribuer toute la topologie, et c'est ce qui se passe dans les protocoles D'État de liaison, tels que OSPF et ISIS.
Dijkstra Algo
Dijkstra algo n'est pas capable de faire la différence entre Négatif de pondération de bord cycle est présent dans le graphique ou pas
1. Poids de bord positif: - Dijkstra toujours PASS si tout le poids de bord dans un graphique est positif
2. Bord négatif wt. et Pas -ve bord wt. cycle: - Dijkstra toujours PASS même si nous avons certains bords sont négatifs, mais pas de cycle / boucle dans le graphique ayant un poids de bord négatif.
[I. e il N'y a pas de cycle négatif de poids de bord]
3. Bord négatif wt. et cinq de bord de wt. cycle: - Dijkstra RÉUSSITE / ÉCHEC même si nous avons certains bords poids comme négatif avec cycle/boucle dans le graphique ayant le poids de bord négatif.
je ne suis pas complètement d'accord, la différence est dans la mise en œuvre et de la complexité de l'algorithme de Dijsktra est plus rapide (O(n^2)), mais difficile à mettre en œuvre, tout en Bellman Ford complexité est O(n^3), mais est plus facile à mettre en œuvre.