Algoritmo de Bellman Ford
Al igual que otros problemas de programación dinámica , el algoritmo calcula las rutas más cortas de forma ascendente. Primero calcula las distancias más cortas que tienen como máximo un borde en la ruta. Luego, calcula los caminos más cortos con 2 aristas como máximo, y así sucesivamente. Después de la i-ésima iteración del bucle exterior, se calculan los caminos más cortos con como máximo i bordes. Puede haber un máximo de |V| – 1 arista en cualquier camino simple, por eso el bucle exterior corre |v| – 1 vez. La idea es, asumiendo que no hay un ciclo de peso negativo si hemos calculado las rutas más cortas con como máximo aristas i, entonces una iteración sobre todas las aristas garantiza dar la ruta más corta con aristas como máximo (i+1)
Algoritmo de
Dijkstra El algoritmo de Dijkstra es muy similar al algoritmo de Prim para el árbol de expansión mínimo. Al igual que el MST de Prim, generamos un SPT (árbol de ruta más corta) con una fuente dada como raíz. Mantenemos dos conjuntos, un conjunto contiene vértices incluidos en el árbol de ruta más corta, otro conjunto incluye vértices que aún no están incluidos en el árbol de ruta más corta. En cada paso del algoritmo, encontramos un vértice que está en el otro conjunto (conjunto de aún no incluido) y tiene una distancia mínima de la fuente.
Diferencias entre el algoritmo de Bellman Ford y el de Dijkstra:
El algoritmo de Bellman Ford y el algoritmo de Dijkstra son algoritmos de ruta más corta de fuente única, es decir, ambos determinan la distancia más corta de cada vértice de un gráfico desde un vértice de fuente única. Sin embargo, hay algunas diferencias clave entre ellos. Seguimos el enfoque de Programación Dinámica en el algoritmo de Bellman Ford y el enfoque Greedy en el algoritmo de Dijkstra. Veamos las otras diferencias principales entre estas dos técnicas:
| Algoritmo de Bellman Ford | Algoritmo de Dijkstra |
|---|---|
| El algoritmo de Bellman Ford funciona cuando hay un borde de peso negativo, también detecta el ciclo de peso negativo. | El algoritmo de Dijkstra puede o no funcionar cuando hay un borde de peso negativo. Pero definitivamente no funcionará cuando haya un ciclo de peso negativo. |
| El resultado contiene los vértices que contienen la información sobre los otros vértices a los que están conectados. | El resultado contiene los vértices que contienen información completa sobre la red, no solo los vértices a los que están conectados. |
| Se puede implementar fácilmente de forma distribuida. | No se puede implementar fácilmente de forma distribuida. |
| Consume más tiempo que el algoritmo de Dijkstra. Su complejidad temporal es O(VE). | Consume menos tiempo. La complejidad temporal es O(E logV). |
| Se toma un enfoque de programación dinámica para implementar el algoritmo. | Se toma un enfoque codicioso para implementar el algoritmo. |
| El algoritmo de Bellman Ford tiene más gastos generales que el algoritmo de Dijkstra. | El algoritmo de Dijkstra tiene menos gastos generales que el algoritmo de Bellman Ford. |
| El algoritmo de Bellman Ford tiene menos escalabilidad que el algoritmo de Dijkstra. | El algoritmo de Dijkstra tiene más escalabilidad que el algoritmo de Bellman Ford. . |