Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford es un algoritmo que calcula los caminos más cortos desde un único vértice de origen a todos los demás vértices en un digrafo ponderado . ^{[ 1 ]} Es más lento que el algoritmo de Dijkstra para el mismo problema, pero más versátil, ya que es capaz de manejar grafos en los que algunos de los pesos de las aristas son números negativos. ^{[ 2 ]} El algoritmo fue propuesto por primera vez por Alfonso Shimbel ( 1955 ) , pero en realidad lleva el nombre de Richard Bellman y Lester Ford Jr. , quienes lo publicaron en 1958 y 1956 , respectivamente. ^{[ 3 ]} Edward F. Moore también publicó una variación del algoritmo en 1959 , y por esta razón también se le llama a veces algoritmo de Bellman-Ford-Moore . ^{[ 1 ]} 

Los pesos negativos de las aristas se encuentran en diversas aplicaciones de grafos. Por eso este algoritmo es útil. ^{[ 4 ]} Si un grafo contiene un "ciclo negativo" (es decir, un ciclo cuyas aristas suman un valor negativo) que es alcanzable desde el origen, entonces no hay un camino más barato : cualquier camino que tenga un punto en el ciclo negativo puede hacerse más barato con un recorrido adicional alrededor del ciclo negativo. En tal caso, el algoritmo de Bellman-Ford puede detectar e informar sobre el ciclo negativo. ^{[ 1 ] [ 5 ]}

Al igual que el algoritmo de Dijkstra , el algoritmo de Bellman-Ford procede mediante relajación , en la que las aproximaciones a la distancia correcta se reemplazan por otras mejores hasta que finalmente se alcanza la solución. En ambos algoritmos, la distancia aproximada a cada vértice siempre sobreestima la distancia real y se reemplaza por el mínimo entre su valor anterior y la longitud de un camino recién encontrado. ^{[ 6 ]}

Sin embargo, el algoritmo de Dijkstra utiliza una cola de prioridad para seleccionar de forma voraz el vértice más cercano que aún no ha sido 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${\displaystyle |V|-1}$tiempos, donde${\displaystyle |V|}$es el número de vértices en el grafo. ^{[ 6 ]}

En cada una de estas repeticiones, el número de vértices con distancias calculadas correctamente aumenta, de lo cual se deduce que, finalmente, 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 el algoritmo de Dijkstra. Las respuestas intermedias y las elecciones entre caminos igualmente cortos dependen del orden en que se relajan las aristas, pero las distancias finales permanecen iguales. ^{[ 6 ]}

Bellman–Ford corre en${\displaystyle O(|V|\cdot |E|)}$tiempo , donde${\displaystyle |V|}$y${\displaystyle |E|}$son el número de vértices y aristas respectivamente.

función BellmanFord( lista de vértices, lista de aristas, origen de vértices ) es// Esta implementación toma un grafo, representado como // listas de vértices (representados como enteros [0..n-1]) y // aristas, y llena dos arreglos (distancia y predecesor) // que contienen el camino más corto desde el origen hasta cada vértice. distancia := lista de tamaño n predecesor := lista de tamaño n// Paso 1: inicializar el grafo para cada vértice v en vértices hacer // Inicializa la distancia a todos los vértices a infinito. distancia[v] := infinito // Y tener un predecesor nulo predecesor[v] := null // La distancia desde la fuente a sí misma es cero. distancia[origen] := 0 // Paso 2: relajar los bordes repetidamente repetir |V|−1 veces : para cada borde (u, v) con peso w en los bordes hacer si distancia[u] + w < distancia[v] entonces distancia[v] := distancia[u] + w predecesor[v] := u // Paso 3: comprobar si hay ciclos de peso negativo para cada arista (u, v) con peso w en las aristas hacer si distancia[u] + w < distancia[v] entonces predecesor[v] := u // Existe un ciclo negativo; // encuentra un vértice en el ciclo visited := lista de tamaño n inicializada con false visited[v] := true while not visited[u] do visited[u] := true u := predecesor[u] // u es un vértice en un ciclo negativo, // encuentra el ciclo en sí. nciclo := [u] v := predecesor[u] mientras v != u hacer nciclo := concatenar([v], nciclo) v := predecesor[v] error "El gráfico contiene un ciclo de peso negativo", ncycle devuelve distancia, predecesor

En pocas palabras, el algoritmo inicializa la distancia al origen en 0 y la de todos los demás nodos en infinito. Luego, para todas las aristas, si la distancia al destino se puede acortar tomando la arista, la distancia se actualiza al nuevo valor menor.

El núcleo del algoritmo es un bucle que escanea todos los bordes en cada iteración. Para cada${\displaystyle i\leq |V|-1}$, al final de la${\displaystyle i}$La -ésima iteración, desde cualquier vértice v , siguiendo el rastro del predecesor registrado en el predecesor produce un camino que tiene un peso total que es como máximo distancia[v] , y además, distancia[v] es un límite inferior a la longitud de cualquier camino desde la fuente hasta v que utiliza como máximo i aristas.

Dado que el camino más largo posible sin ciclo puede ser${\displaystyle |V|-1}$bordes, los bordes deben ser escaneados${\displaystyle |V|-1}$veces para asegurar que se haya encontrado el camino más corto para todos los nodos. Se realiza un escaneo final de todos los bordes y si se actualiza alguna distancia, entonces un camino de longitud${\displaystyle |V|}$Se han encontrado aristas que solo pueden aparecer si existe al menos un ciclo negativo en el grafo.

La arista (u, v) encontrada en el paso 3 debe ser alcanzable desde un ciclo negativo, pero no necesariamente forma parte del ciclo en sí, por lo que es necesario seguir la ruta de los predecesores hacia atrás hasta detectar un ciclo. El pseudocódigo anterior utiliza una matriz booleana ( visited) para encontrar un vértice en el ciclo, pero se puede usar cualquier algoritmo de detección de ciclos para encontrar un vértice en el ciclo.

Una mejora común al implementar el algoritmo es regresar anticipadamente cuando una iteración del paso 2 no logra relajar ningún borde, lo que implica que se han encontrado todos los caminos más cortos y, por lo tanto, no hay ciclos negativos. En ese caso, la complejidad del algoritmo se reduce de${\displaystyle O(|V|\cdot |E|)}$a${\displaystyle O(l\cdot |E|)}$dónde${\displaystyle l}$es la longitud máxima del camino más corto en el grafo.

La corrección del algoritmo se puede demostrar por inducción : ^{[ 2 ] [ 7 ]}

Lema . Después de i repeticiones del bucle for ,

• Si Distance( u ) no es infinito, es igual a la longitud de algún camino desde s hasta u ; y
• Si hay un camino de s a u con como máximo i aristas, entonces Distance(u) es como máximo la longitud del camino más corto de s a u con como máximo i aristas.

Demostración . Para el caso base de inducción, consideremos i=0y el momento antes de que el bucle for se ejecute por primera vez. Entonces, para el vértice de origen, source.distance = 0, lo cual es correcto. Para otros vértices u , , lo cual también es correcto porque no hay un camino desde el origen hasta u con 0 aristas.u.distance = infinity

Para el caso inductivo, primero demostramos la primera parte. Consideremos un momento en que la distancia de un vértice se actualiza mediante . Por suposición inductiva, es la longitud de algún camino desde la fuente hasta u . Entonces es la longitud del camino desde la fuente hasta v que sigue el camino desde la fuente hasta u y luego va a v .v.distance := u.distance + uv.weightu.distanceu.distance + uv.weight

Para la segunda parte, consideremos un camino más corto P (puede haber más de uno) desde el origen hasta v con como máximo i aristas. Sea u el último vértice antes de v en este camino. Entonces, la parte del camino desde el origen hasta u es un camino más corto desde el origen hasta u con como máximo i-1 aristas, ya que si no lo fuera, entonces debe haber algún camino estrictamente más corto desde el origen hasta u con como máximo i-1 aristas, y podríamos entonces agregar la arista uv a este camino para obtener un camino con como máximo i aristas que es estrictamente más corto que P —una contradicción. Por suposición inductiva, u.distancedespués de i −1 iteraciones es como máximo la longitud de este camino desde el origen hasta u . Por lo tanto, uv.weight + u.distancees como máximo la longitud de P . En la i ^-ésima iteración, v.distancese compara con uv.weight + u.distance, y se establece igual a él si uv.weight + u.distancees menor. Por lo tanto, después de i iteraciones, v.distancees como máximo la longitud de P , es decir, la longitud del camino más corto desde el origen hasta v que usa como máximo i aristas.

Si no hay ciclos de peso negativo, entonces cada camino más corto visita cada vértice como máximo una vez, por lo que en el paso 3 no se pueden realizar más mejoras. Por el contrario, supongamos que no se puede realizar ninguna mejora. Entonces, para cualquier ciclo con vértices v [0], ..., v [ k −1],

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

Sumando alrededor del ciclo, los términos v [ i ].distancia y v [ i −1 (mod k )].distancia se cancelan, dejando

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

Es decir, cada ciclo tiene un peso no negativo.

Cuando el algoritmo se utiliza para encontrar rutas más cortas, la existencia de ciclos negativos representa un problema, impidiendo que el algoritmo encuentre una respuesta correcta. Sin embargo, dado que finaliza al encontrar un ciclo negativo, el algoritmo de Bellman-Ford puede utilizarse en aplicaciones donde este sea el objetivo a buscar, por ejemplo, en técnicas de cancelación de ciclos en el análisis de flujo de red . ^{[ 1 ]}

Una variante distribuida del algoritmo de Bellman-Ford se utiliza en protocolos de enrutamiento de vector distancia , por ejemplo, el Protocolo de Información de Enrutamiento (RIP). ^{[ 8 ]} El algoritmo es distribuido porque involucra varios nodos (enrutadores) dentro de un sistema autónomo (AS) , un conjunto de redes IP que generalmente pertenecen a un ISP. Consta de los siguientes pasos:

1. Cada nodo calcula las distancias entre sí mismo y todos los demás nodos dentro del sistema autónomo y almacena esta información en una tabla.
2. Cada nodo envía su tabla a todos los nodos vecinos.
3. Cuando un nodo recibe tablas de distancias de sus vecinos, calcula las rutas más cortas a todos los demás nodos y actualiza su propia tabla para reflejar cualquier cambio.

Las principales desventajas del algoritmo de Bellman-Ford en este contexto son las siguientes:

• No es escalable.
• Los cambios en la topología de la red no se reflejan rápidamente, ya que las actualizaciones se propagan nodo por nodo.
• Si los fallos en los enlaces o en los nodos hacen que un nodo sea inaccesible desde un conjunto de otros nodos, estos pueden pasar una eternidad aumentando gradualmente sus estimaciones de la distancia a dicho nodo, y mientras tanto pueden producirse bucles de enrutamiento.

El algoritmo de Bellman-Ford puede mejorarse en la práctica (aunque no en el peor de los casos) al observar que, si una iteración del bucle principal del algoritmo termina sin realizar ningún cambio, el algoritmo puede terminarse inmediatamente, ya que las iteraciones subsiguientes no realizarán más cambios. Con esta condición de terminación temprana, el bucle principal puede en algunos casos utilizar muchas menos de | V |  −  1 iteraciones, aunque el peor caso del algoritmo permanezca sin cambios. Las siguientes mejoras mantienen el${\displaystyle O(|V|\cdot |E|)}$complejidad temporal en el peor de los casos.

Una variación del algoritmo de Bellman-Ford descrito por Moore (1959) reduce el número de pasos de relajación necesarios en cada iteración. Si un vértice v tiene un valor de distancia que no ha cambiado desde la última vez que se relajaron las aristas que salen de v , no es necesario relajarlas una segunda vez. De esta forma, a medida que aumenta el número de vértices con valores de distancia correctos, disminuye el número de aristas salientes que deben relajarse en cada iteración, lo que resulta en un ahorro de tiempo constante para grafos densos . Esta variación se puede implementar manteniendo una colección de vértices cuyas aristas salientes deben relajarse, eliminando un vértice de esta colección cuando sus aristas se relajan y añadiendo a la colección cualquier vértice cuyo valor de distancia cambie tras un paso de relajación. En China, este algoritmo fue popularizado por Fanding Duan, quien lo redescubrió en 1994 como el "algoritmo de camino más corto más rápido". ^{[ 9 ]}

Yen (1970) describió otra mejora al algoritmo de Bellman-Ford. Su mejora primero asigna un orden lineal arbitrario a todos los vértices y luego divide el conjunto de todas las aristas en dos subconjuntos. El primer subconjunto, E _f , contiene todas las aristas ( v _i , v _j ) tales que i < j ; el segundo, E _b , contiene las aristas ( v _i , v _j ) tales que i > j . Cada vértice se visita en el orden v ₁ , v ₂ , ..., v _{| V |} , relajando cada arista saliente de ese vértice en E _f . Luego, cada vértice se visita en el orden v _{| V |} , v _{| V |−1} , ..., v ₁ , relajando cada arista saliente de ese vértice en E _b . Cada iteración del bucle principal del algoritmo, después de la primera, agrega al menos dos aristas al conjunto de aristas cuyas distancias relajadas coinciden con las distancias correctas del camino más corto: una de E _f y una de E _b . Esta modificación reduce el número de iteraciones en el peor de los casos del bucle principal del algoritmo de | V |  −  1 a${\displaystyle |V|/2}$. ^{[ 10 ] [ 11 ]}

Otra mejora, propuesta por Bannister y Eppstein (2012) , reemplaza el orden lineal arbitrario de los vértices utilizado en la segunda mejora de Yen por una permutación aleatoria . Este cambio hace que el peor caso para la mejora de Yen (en el que las aristas de un camino más corto alternan estrictamente entre los dos subconjuntos E _f y E _b ) sea muy improbable. Con un ordenamiento de vértices permutado aleatoriamente, el número esperado de iteraciones necesarias en el bucle principal es como máximo${\displaystyle |V|/3}$. ^{[ 11 ]}

Fineman (2024) , en la Universidad de Georgetown , creó un algoritmo mejorado que con alta probabilidad se ejecuta en${\displaystyle {\tilde {O}}(|V|^{8/9}\cdot |E|)}$tiempo . Aquí, el${\displaystyle {\tilde {O}}}$es una variante de la notación O grande que oculta los factores logarítmicos.