algorithm - floyd - Bellman-Ford vs Dijkstra: ¿En qué circunstancias es mejor Bellman-Ford?

dijkstra algorithm c++

Question

Después de muchas búsquedas en Google, he encontrado que la mayoría de las fuentes dicen que el algoritmo Dijkstra es "más eficiente" que el algoritmo Bellman-Ford. Pero, ¿en qué circunstancias el algoritmo de Bellman-Ford es mejor que el algoritmo de Dijkstra?

Sé que "mejor" es una declaración amplia, por lo que específicamente quiero decir en términos de velocidad y también de espacio si eso se aplica. Seguramente hay una situación en la que el enfoque de Bellman-Ford es mejor que el enfoque de Dijkstra.

Answer 1

Como ya se indicó en la respuesta elegida, Bellman-Ford realiza la comprobación de todos los vértices, Dijkstra solo en el que tiene la mejor distancia calculada hasta el momento. Una vez más señalado, esto mejora la complejidad del enfoque de Dijkstra, sin embargo, requiere comparar todos los nodos para averiguar el valor de la distancia mínima. Como esto no es 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 por vector de distancia (por ejemplo, RIP e IGRP), donde se usa principalmente información local. Para usar Dijkstra en los protocolos de enrutamiento, en su lugar, primero es necesario distribuir la topología completa, y esto es lo que sucede en los protocolos de estado de enlace, como OSPF e ISIS.

Answer 2

La única diferencia es que el algoritmo de Dijkstra no puede manejar pesos de borde negativos que maneja Bellman-ford. Y Bellman-ford también nos dice si la gráfica contiene un ciclo negativo. Si el gráfico no contiene bordes negativos, entonces Dijkstra siempre es mejor.

Una alternativa eficiente para Bellman-ford es Directed Acyclic Graph (DAG), que utiliza la clasificación topológica.

http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

Answer 3

No estoy completamente de acuerdo, la diferencia está en la implementación y la complejidad, el algoritmo de Dijsktra es más rápido (O (n ^ 2)) pero difícil de implementar, mientras que la complejidad de Bellman Ford es O (n ^ 3) pero es más fácil de implementar.

Answer 4

Dijkstra Algo
Dijkstra algo no es capaz de diferenciar entre el peso negativo del borde. El ciclo está presente en la gráfica o no.

1. Peso de borde positivo: - Dijkstra siempre PASA si todo el peso de borde en un gráfico es positivo
2. Peso negativo del borde. y No -ve edge wt. ciclo: - Dijkstra PASA siempre aunque tengamos un poco de ponderación de bordes como Negativo pero NO hay ciclo / bucle en el gráfico que tenga una ponderación de borde negativa.
[es decir, no hay un ciclo de peso de borde negativo presente]
3. Peso negativo del borde. y el borde de peso ciclo: - Dijkstra puede APROBAR / FALLO incluso si tenemos un peso negativo de los bordes junto con un ciclo / bucle en el gráfico que tiene un peso negativo del borde.

Answer 5

El algoritmo de Bellman-Ford es un algoritmo de ruta más corta de una sola fuente, por lo que cuando tiene un peso de borde negativo, entonces puede detectar ciclos negativos en un gráfico.

La única diferencia entre dos es que Bellman Ford también es capaz de manejar pesos negativos, mientras que el algoritmo 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; en contraste, el algoritmo de Bellman-Ford simplemente relaja todos los bordes y hace esto | V | - 1 vez, donde | V | es el número de vértices en la gráfica. En cada una de estas repeticiones, el número de vértices con distancias calculadas correctamente crece, de lo que se deduce que, finalmente, todos los vértices tendrán sus distancias correctas. Este método permite que el algoritmo de Bellman-Ford se aplique a una clase más amplia de entradas que Dijkstra.

Sin embargo, Dijkstra generalmente se considera mejor en ausencia de bordes de peso negativo, ya que una implementación típica de la cola de prioridad de pila binaria tiene O ((| E | + | V |) log | V |) complejidad de tiempo [Una cola de prioridad de pila Fibonacci da O ( | V | log | V | + | E |)], mientras que el algoritmo de Bellman-Ford tiene una complejidad O (| V || E |)