networking - ppt - como funciona bellman ford

diferencia entre Bellman Ford y el algoritmo de Dijkstra

Question

   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

Ok, este es el gráfico. Mi nodo de origen es 1 y el nodo de destino es 5

Mi pregunta es.

¿Ambos algoritmos van a dar el mismo resultado o no? Es decir, ¿regresarán los dos 1->2->4->5 ? (Excepto que los pesos negativos no están permitidos en dijkstra)

Gracias de antemano por la ayuda.

Answer 1

El algoritmo Bellman-Ford es un algoritmo de ruta más corta de fuente única, que permite un peso de borde negativo y puede detectar ciclos negativos en un gráfico.

El algoritmo de Dijkstra es también otro algoritmo de ruta más corta de fuente única. Sin embargo, el peso de todos los bordes debe ser no negativo.

Para su caso, en lo que respecta al costo total, no habrá diferencia, ya que los bordes en el gráfico tienen un peso no negativo. Sin embargo, el algoritmo de Dijkstra se usa generalmente, ya que la implementación típica con el montón binario tiene una complejidad de tiempo Theta((|E|+|V|)log|V|) , mientras que el algoritmo de Bellman-Ford tiene O(|V||E|) complejidad.

Si hay más de 1 ruta que tiene un costo mínimo, la ruta real devuelta depende de la implementación (incluso para el mismo algoritmo).

Answer 2

Los vértices en el algoritmo de Dijkstra contienen toda la información de una red. No existe tal cosa que cada vértice solo se preocupe por sí mismo y sus vecinos. Por otro lado, los nodos del algoritmo de Bellman-Ford solo contienen la información relacionada. Esta información permite que ese nodo simplemente sepa a qué nodos vecinos se puede conectar y al nodo del que proviene la relación, mutuamente. El algoritmo de Dijkstra es más rápido que el algoritmo de Bellman-Ford; sin embargo, el segundo algoritmo puede ser más útil para resolver algunos problemas, como los pesos negativos de las rutas.