Bellman-Ford vs Dijkstra: ¿En qué circunstancias es mejor Bellman-Ford?
Después de mucho buscar 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 es mejor el algoritmo Bellman-Ford que el algoritmo Dijkstra?
Sé que "mejor" es una declaración amplia, así que específicamente me refiero en términos de velocidad y también espacio si eso se aplica. Seguramente hay alguna situación en la que el enfoque Bellman-Ford es mejor que el enfoque Dijkstra.
5 answers
El algoritmo Bellman-Ford es un algoritmo de ruta más corta de una sola fuente, por lo que cuando tiene un peso de borde negativo, 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.
Desde 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 esta proceso de relajación en todos sus bordes salientes; en contraste, el algoritmo 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, el número de vértices con distancias calculadas correctamente crece, desde que se deduce que eventualmente todos los vértices tendrán su correcta distancia. Este método permite aplicar el algoritmo 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 O ((|E|+|V|) log|V|) complejidad temporal [Una cola de prioridad de montón de Fibonacci da O (|V| log |V| + |E|)], mientras que el algoritmo de Bellman-Ford tiene O (|V| / E/) complejidad
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-10-17 07:20:05
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 el gráfico contiene ciclo negativo. Si el gráfico no contiene bordes negativos, entonces el de Dijkstra siempre es mejor.
Una alternativa eficiente para Bellman-ford es el Grafo Acíclico Dirigido (DAG) que utiliza la clasificación topológica.
Http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs /
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-09-22 15:49:54
Como ya se indicó en la respuesta elegida, Bellman-Ford realiza la comprobación en todos los vértices, Dijkstra solo en el que tenga la mejor distancia calculada hasta el momento. Una vez más ya se ha señalado, esto mejora la complejidad del enfoque Dijkstra, sin embargo, requiere comparar todos los nodos para averiguar el valor de distancia mínima. Al no ser esto necesario en el Bellman-Ford, es más fácil de implementar en un entorno distribuido. Es por eso que se utiliza en los protocolos de enrutamiento de Vectores de distancia (p. ej., RIP e IGRP), donde se utiliza principalmente información local. Para usar Dijkstra en protocolos de enrutamiento, en cambio, es necesario primero distribuir toda la topología, y esto es lo que sucede en protocolos de Estado de enlace, como OSPF e ISIS.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-10-24 11:59:26
Dijkstra Algo
Dijkstra algo no es capaz de diferenciar entre Ciclo de peso de borde negativo está presente en el gráfico o no
1. Peso del borde positivo: - Dijkstra siempre PASS si todo el peso del borde en un gráfico es positivo
2. Peso del borde negativo. y No-ve edge wt. ciclo: - Dijkstra siempre PASAR incluso si tenemos algunos bordes peso como negativo, pero NINGÚN ciclo / bucle en el gráfico que tiene borde negativo peso.
[es decir, no hay un ciclo de peso de borde negativo presente]
3. Peso del borde negativo. and-ve edge wt. ciclo: - Dijkstra mayo PASS / FAIL incluso si tenemos algunos bordes peso como negativo junto con ciclo/bucle en el gráfico que tiene peso de borde negativo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-08-19 13:06:35
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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-06-29 14:19:05