Arturo, miembro de nuestro equipo de trabajo, nos hizo el favor de crear este tutorial porque domina perfectamente el tema.
Solución:
El algoritmo Bellman-Ford es un algoritmo de ruta más corta de fuente única, por lo que cuando tiene un peso de borde negativo, puede detectar ciclos negativos en un gráfico.
La única diferencia entre los dos es que Bellman-Ford también es capaz de manejar pesos negativos, mientras que el algoritmo de Dijkstra solo puede manejar positivos.
de wiki
Sin embargo, el algoritmo de Dijkstra selecciona con avidez el nodo de peso mínimo que aún no se ha procesado y realiza este proceso de relajación en todos sus bordes salientes; por el contrario, el algoritmo de Bellman-Ford simplemente relaja todos los bordes y hace esto |V | − 1 veces, donde |V | es el número de vértices en el gráfico. En cada una de estas repeticiones crece el número de vértices con distancias correctamente calculadas, de lo que se deduce que eventualmente todos los vértices tendrán sus distancias correctas. Este método permite aplicar el algoritmo de Bellman-Ford a una clase más amplia de entradas que Dijkstra.
Sin embargo, Dijkstra generalmente se considera mejor en ausencia de bordes de peso negativos, ya que una implementación típica de cola de prioridad de montón binario tiene una complejidad de tiempo O((|E|+|V|)log|V|) [A Fibonacci heap priority queue gives O(|V|log|V| + |E|)]mientras que el algoritmo Bellman-Ford tiene una complejidad O(|V||E|)
Como ya se indicó en la respuesta elegida, Bellman-Ford realiza la verificación en todos los vértices, Dijkstra solo en el que tiene la mejor distancia calculada hasta el momento. Nuevamente, ya se señaló, esto mejora la complejidad del enfoque de Dijkstra, sin embargo, requiere comparar todos los vértices para encontrar el valor de distancia mínima. Siendo esto no necesario en Bellman-Ford, es más fácil de implementar en un entorno distribuido. Es por eso que se usa en los protocolos de enrutamiento de vector de distancia (p. ej., RIP e IGRP), donde se usa principalmente información local. Para usar Dijkstra en protocolos de enrutamiento, en cambio, primero es necesario distribuir toda la topología, y esto es lo que sucede en los protocolos Link State, como OSPF e ISIS.
La única diferencia es que el algoritmo de Dijkstra no puede manejar los pesos de borde negativos que maneja Bellman-ford. Y bellman-ford también nos dice si el gráfico contiene un ciclo negativo. Si el gráfico no contiene bordes negativos, el de Dijkstra siempre es mejor.
Una alternativa eficiente para Bellman-ford es el gráfico acíclico dirigido (DAG) que utiliza clasificación topológica.
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
Aquí puedes ver las reseñas y valoraciones de los usuarios
Si crees que te ha resultado provechoso este artículo, sería de mucha ayuda si lo compartieras con el resto juniors de este modo nos ayudas a dar difusión a nuestro contenido.