2 1 1----------2---------4 | | | |3 |3 |1 | 6 | | 3---------5 --------- Ok, so this is the graph. My source node is 1 and destination node is 5My question is.Are both the algorithms going to give the same output or not? That is, will both return 1->2->4->5? (Except that negative weights are not allowed in dijkstra's)Thanks in advance for help.
3 Réponses :
L'algorithme Bellman-Ford est un algorithme de chemin le plus court à la source unique, ce qui permet un poids de bord négatif et peut détecter des cycles négatifs dans un graphique.
Algorithme de Dijkstra est également un autre algorithme de chemin le plus court unique. Cependant, le poids de tous les bords doit être non négatif.
Pour votre cas, en ce qui concerne le coût total, il n'y aura aucune différence, car les bords du graphique ont un poids non négatif. Cependant, l'algorithme de Dijkstra est généralement utilisé, car la mise en œuvre typique avec le tas binaire a S'il y a plus d'un chemin qui a un coût minimum, le chemin réel renvoyé est en fonction de la mise en œuvre (même pour le même algorithme). theta ((| e | + | + | v |) journal | v |) complexité de temps, tandis que Bellman-Ford Algorithm a O (| v || e |) complexité.
J'aimerais ajouter que pour un réseau de nœuds distribués, Dijkstra nécessite un contrôle centralisé (vous devez avoir une liste ouverte globale, etc.), tandis que Bellman-Ford n'est pas (chaque noeud met simplement à jour les voisins des changements). Ils sont connus dans la mise en réseau de lingo comme état lié, et des algorithmes de vecteur de distance respectivement. [J'espère que ce n'est pas trop vague pour comprendre ...]
Les sommets de l'algorithme de Dijkstra contiennent toutes les informations d'un réseau. Il n'y a pas de telle chose que chaque sommet ne se soucie que de lui-même et de ses voisins. D'autre part, l'algorithme de Bellman-Ford a NodeScontain uniquement les informations liées à. Ces informations permettent à ce nœud de connaître les nœuds voisins pouvant se connecter et que le nœud proviennent de la relation, mutuellement. L'algorithme de Dijkstra est plus rapide que l'algorithme de Bellman-Ford, mais le deuxième algorithme peut être plus utile pour résoudre certains problèmes, tels que des poids négatifs des chemins.
L'algorithme Djikstra est une technique gourmande où, selon la mise en œuvre d'algorithme de Bellmanford, nous avons besoin d'une approche dynamique.
Dans Djikstra Algo, nous nous détendons de chaque noeud / sommet dans une boucle où, comme dans Bellmanford Algo, nous effectuons une détente uniquement | V-1 | fois.
L'algo Dijkstra convient au graphique lorsqu'il est positif, et échoue dans le cas d'un graphe tranchant négatif où, à mesure que le Bellmanford Algo dispose d'un avantage sur Djikstra qu'elle peut mettre en œuvre même lorsque le poids du bord est affecté négativement. .
Le Bellmanford peut déterminer si la solution graphique existe ou non (c'est-à-dire que le graphique dirigé a un cycle de poids négatif ou non) où l'algo Djikatra ne fait pas de même.
La complexité temporelle de Djikstra Algo est O (v ^ 2) lorsqu'elle est mise en œuvre par une matrice linéaire, O (E.Log V) lorsqu'il est mis en œuvre avec binay tas ou fibonacci heap où Bellmanford algo a O (| V | e | E | ) complexité du temps.