El algoritmo Bellman-Ford es un algoritmo que calcula las rutas más cortas desde un único vértice fuente hasta todos los demás vértices en un dígrafo 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 gráficos en los que algunos de los pesos de los bordes son números negativos. [2] El algoritmo fue propuesto por primera vez por Alfonso Shimbel (1955), pero 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 a veces también se le llama algoritmo Bellman-Ford-Moore . [1]
Los pesos de borde negativos se encuentran en diversas aplicaciones de gráficos. Por eso este algoritmo es útil. [4] Si un gráfico contiene un "ciclo negativo" (es decir, un ciclo cuyos bordes suman un valor negativo) al que se puede acceder desde la fuente, entonces no existe un camino más barato : cualquier camino que tenga un punto en el ciclo negativo puede ser abaratado por una vuelta más alrededor del ciclo negativo. En tal caso, el algoritmo de Bellman-Ford puede detectar e informar el ciclo negativo. [ 15]
Al igual que el algoritmo de Dijkstra , Bellman-Ford procede por relajación , en el que las aproximaciones a la distancia correcta se reemplazan por otras mejores hasta que finalmente alcanzan la solución. En ambos algoritmos, la distancia aproximada a cada vértice es siempre una sobreestimación de la distancia verdadera y se reemplaza por el mínimo de su valor anterior y la longitud de un camino recién encontrado.
Sin embargo, el algoritmo de Dijkstra utiliza una cola de prioridad para seleccionar con avidez 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 todas las aristas y lo hace multiplicado por donde está el número de vértices del gráfico.
En cada una de estas repeticiones crece el número de vértices con distancias calculadas correctamente, de lo que se deduce que eventualmente 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 dependen del orden de las aristas relajadas, pero la respuesta final sigue siendo la misma.
Bellman-Ford se ejecuta en el tiempo , donde y son el número de vértices y aristas respectivamente.
La función BellmanFord ( lista de vértices, lista de bordes, fuente de vértices ) es // Esta implementación toma un gráfico, representado como // listas de vértices (representados como números enteros [0..n-1]) y aristas, // y llena dos matrices (distancia y predecesor) que contienen // el camino más corto desde la fuente a cada vértice distancia := lista de tamaño n predecesor := lista de tamaño n // Paso 1: inicializa el gráfico para cada vértice v en los vértices // Inicializa la distancia a todos los vértices hasta el infinito distancia[v] := inf // Y tener un predecesor nulo predecesor[v] := nulo // La distancia desde la fuente a sí mismo es, por supuesto, cero distancia[fuente] := 0 // Paso 2: relajar los bordes repetir repetidamente |V|−1 veces : para cada borde (u, v) con peso w en los bordes , hazlo si distancia[u] + w < distancia[v] entonces distancia[v] := distancia[u] + w predecesor[v] := u // Paso 3: verifique los ciclos de peso negativo para cada borde (u, v) con peso w en los bordes . Si distancia[u] + w < distancia[v] , entonces predecesor[v] := u // Existe un ciclo negativo; encontrar un vértice en el ciclo visitado := lista de tamaño n inicializada con falso visitado[v] := verdadero mientras no visitado[u] sí visitado[u] := verdadero tu := predecesor[u] // u es un vértice en un ciclo negativo, encuentra el ciclo en sí nciclo := [u] v := predecesor[u] mientras v != lo haces nciclo := concatenar([v], nciclo) v := predecesor[v] error "El gráfico contiene un ciclo de peso negativo", distancia de retorno del ciclo , predecesor
En pocas palabras, el algoritmo inicializa la distancia a la fuente en 0 y todos los demás nodos en infinito. Luego, para todos los bordes, si la distancia hasta el destino se puede acortar tomando el borde, la distancia se actualiza al nuevo valor inferior.
El núcleo del algoritmo es un bucle que escanea todos los bordes en cada bucle. Para cada , al final de la -ésima iteración, desde cualquier vértice v , seguir el camino 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 de la longitud de cualquier ruta desde el origen hasta v que utilice como máximo i bordes.
Dado que la ruta más larga posible sin un ciclo pueden ser los bordes, los bordes deben escanearse varias veces para garantizar que se haya encontrado la ruta más corta para todos los nodos. Se realiza un escaneo final de todos los bordes y, si se actualiza alguna distancia, se ha encontrado una ruta de bordes de longitud que solo puede ocurrir si existe al menos un ciclo negativo en el gráfico.
El borde (u, v) que se encuentra en el paso 3 debe ser alcanzable desde un ciclo negativo, pero no necesariamente es parte del ciclo en sí, por lo que es necesario seguir el camino de los predecesores hacia atrás hasta que se detecte 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 búsqueda de ciclos para encontrar un vértice en el ciclo.
Una mejora común al implementar el algoritmo es regresar temprano 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 desde hasta donde está la longitud máxima de la ruta más corta en el gráfico.
La exactitud del algoritmo se puede demostrar por inducción : [2]
Lema . Después de i repeticiones del bucle for ,
Prueba . Para el caso base de inducción, considere i=0y el momento antes de que se ejecute el bucle for por primera vez. Luego, para el vértice de origen, source.distance = 0lo cual es correcto. Para otros vértices u , lo cual también es correcto porque no hay un camino desde la fuente hasta u con 0 aristas.u.distance = infinity
Para el caso inductivo, primero demostramos la primera parte. Considere un momento en el que la distancia de un vértice se actualiza con v.distance := u.distance + uv.weight. Por suposición inductiva, u.distancees la longitud de algún camino desde la fuente hasta u . Entonces u.distance + uv.weightes la longitud del camino desde la fuente hasta v que sigue el camino desde la fuente hasta u y luego va a v .
Para la segunda parte, considere un camino más corto P (puede haber más de uno) desde la fuente 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 la fuente hasta u es un camino más corto desde la fuente 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 la fuente hasta u con como máximo i-1. 1 aristas, y luego podríamos agregar la arista uv a este camino para obtener un camino con como máximo i aristas que sea 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 la fuente hasta u . Por 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.distancey se iguala 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 la fuente hasta v que utiliza como máximo i bordes.
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 hacer 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 ].distance y v [ i −1 (mod k )].distance 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 caminos más cortos, la existencia de ciclos negativos es un problema que impide que el algoritmo encuentre una respuesta correcta. Sin embargo, dado que termina al encontrar un ciclo negativo, el algoritmo de Bellman-Ford se puede utilizar para aplicaciones en las que este es 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 Bellman-Ford se utiliza en los protocolos de enrutamiento por vector distancia , por ejemplo el Protocolo de información de enrutamiento (RIP). El algoritmo se distribuye porque involucra varios nodos (enrutadores) dentro de un sistema autónomo (AS) , una colección de redes IP que normalmente pertenece a un ISP. Consta de los siguientes pasos:
Las principales desventajas del algoritmo Bellman-Ford en este contexto son las siguientes:
El algoritmo Bellman-Ford puede mejorarse en la práctica (aunque no en el peor de los casos) mediante la observación de 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 posteriores lo harán. no hacer más cambios. Con esta condición de terminación anticipada, el bucle principal puede, en algunos casos, utilizar muchos menos de | V | − 1 iteración, aunque el peor caso del algoritmo permanece sin cambios. Todas las siguientes mejoras mantienen la complejidad del tiempo 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 que deben realizarse dentro de cada iteración del algoritmo. Si un vértice v tiene un valor de distancia que no ha cambiado desde la última vez que se relajaron los bordes de v , entonces no hay necesidad de relajar los bordes de v por segunda vez. De esta manera, a medida que crece el número de vértices con valores de distancia correctos, el número cuyos bordes salientes deben relajarse en cada iteración se reduce, lo que genera un ahorro de tiempo de factor constante para gráficos densos . Esta variación se puede implementar manteniendo una colección de vértices cuyos bordes salientes deben relajarse, eliminando un vértice de esta colección cuando sus bordes estén relajados y agregando a la colección cualquier vértice cuyo valor de distancia cambie mediante 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 y más rápido". [6]
Yen (1970) describió otra mejora del algoritmo de Bellman-Ford. Su mejora primero asigna un orden lineal arbitrario en todos los vértices y luego divide el conjunto de todas las aristas en dos subconjuntos. El primer subconjunto, Ef , contiene todas las aristas ( v i , v j ) tales que i < j ; el segundo, E b , contiene aristas ( vi , v j ) tales que i > j . Cada vértice se visita en el orden v 1 , v 2 , ..., v | V | , relajando cada borde saliente desde ese vértice en E f . Luego se visita cada vértice en el orden v | V | , v | V |−1 , ..., v 1 , relajando cada borde 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 de ruta más cortas correctas: una desde E f y otra desde E b . Esta modificación reduce el número de iteraciones del peor de los casos del bucle principal del algoritmo de | V | − 1 a . [7] [8]
Otra mejora, de Bannister y Eppstein (2012), reemplaza el orden lineal arbitrario de los vértices utilizado en la segunda mejora del Yen por una permutación aleatoria . Este cambio hace que sea muy poco probable que se produzca el peor caso para la mejora del yen (en el que los bordes de un camino más corto alternan estrictamente entre los dos subconjuntos E f y E b ). Con un orden de vértices permutado aleatoriamente, el número esperado de iteraciones necesarias en el bucle principal es como máximo . [8]
