Algoritmo de Bellman-Ford

Algoritmo para encontrar los caminos más cortos en grafos

El algoritmo Bellman-Ford es un algoritmo que calcula las rutas más cortas desde un único vértice fuente a 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 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 su lugar 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 lo llama a veces algoritmo Bellman-Ford-Moore . ^[1]

Los pesos de aristas negativos se encuentran en varias 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) al que se puede llegar desde la fuente, entonces no existe una ruta más barata : cualquier ruta que tenga un punto en el ciclo negativo puede volverse más barata mediante una vuelta más alrededor del ciclo negativo. En tal caso, el algoritmo Bellman-Ford puede detectar y reportar el ciclo negativo. ^{[1] [5]}

Algoritmo

En este gráfico de ejemplo, suponiendo que A es la fuente y que los bordes se procesan en el peor orden, de derecha a izquierda, se requieren las iteraciones completas | V |−1 o 4 para que las estimaciones de distancia converjan. Por el contrario, si los bordes se procesan en el mejor orden, de izquierda a derecha, el algoritmo converge en una sola iteración.

Al igual que el algoritmo de Dijkstra , el algoritmo de Bellman-Ford procede por relajación , en el que las aproximaciones a la distancia correcta se reemplazan por otras mejores hasta que finalmente se llega a 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 Bellman-Ford simplemente relaja todos los bordes, y hace esto varias veces, donde es el número de vértices en el gráfico. ${\displaystyle |V|-1}$ ${\displaystyle |V|}$

En cada una de estas repeticiones, el número de vértices con distancias calculadas correctamente aumenta, de lo que se deduce que, al final, todos los vértices tendrán sus distancias correctas. Este método permite aplicar el algoritmo 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. ${\displaystyle O(|V|\cdot |E|)}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$

La función BellmanFord( lista de vértices, lista de aristas, fuente de vértice ) 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  // la ruta más corta desde la fuente hasta cada vértice distancia := lista de tamaño n predecesor := lista de tamaño n // Paso 1: inicializar 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] := null  // La distancia desde la fuente hasta sí misma es, por supuesto, cero. distancia[fuente] := 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: verificar ciclos de peso negativo  para cada borde (u, v) con peso w en los bordes hacer  si distancia[u] + w < distancia[v] entonces predecesor[v] := u // Existe un ciclo negativo; busque un vértice en el ciclo visitado := lista de tamaño n inicializada con falso visitado[v] := verdadero  mientras que  no visitado[u] sí visitado[u] := verdadero u := predecesor[u] // u es un vértice en un ciclo negativo, encuentre el ciclo en sí nciclo := [u] v := predecesor[u] mientras v != u lo haces ncycle := concatenar([v], ncycle) v := predecesor[v] Error "El gráfico contiene un ciclo de peso negativo", distancia de retorno ncycle , predecesor

En pocas palabras, el algoritmo inicializa la distancia hasta 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 recorre todos los bordes en cada bucle. Para cada , al final de la iteración -ésima, desde cualquier vértice v , seguir el rastro del predecesor registrado en predecesor produce una ruta que tiene un peso total que es como máximo distance[v] , y además, distance[v] es un límite inferior para la longitud de cualquier ruta desde la fuente hasta v que utiliza como máximo i bordes. ${\displaystyle i\leq |V|-1}$ ${\displaystyle i}$

Dado que la ruta más larga posible sin un ciclo puede ser la de los bordes, estos 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 longitud de bordes, lo que solo puede ocurrir si existe al menos un ciclo negativo en el gráfico. ${\displaystyle |V|-1}$ ${\displaystyle |V|-1}$ ${\displaystyle |V|}$

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 la ruta 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 utilizar cualquier algoritmo de búsqueda de ciclos para encontrar un vértice en el ciclo.

Una mejora habitual al implementar el algoritmo es volver antes cuando una iteración del paso 2 no logra relajar ninguna arista, 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 a donde es la longitud máxima de un camino más corto en el gráfico. ${\displaystyle O(|V|\cdot |E|)}$ ${\displaystyle O(l\cdot |E|)}$ ${\displaystyle l}$

Prueba de corrección

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

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

• si Distancia( u ) no es infinita, 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 Distancia(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 la 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 = 0, lo cual es correcto. Para otros vértices u , , lo cual también es correcto porque no hay una ruta desde el origen hasta u con 0 aristas.u.distance = infinity

Para el caso inductivo, primero demostramos la primera parte. Consideremos un momento en el que la distancia de un vértice se actualiza mediante 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 hasta 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 aristas, y entonces 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 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 la fuente 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.

Encontrar ciclos negativos

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 Bellman-Ford se puede utilizar para aplicaciones en las que este es el objetivo que se busca, por ejemplo, en técnicas de cancelación de ciclos en el análisis de flujo de red . ^[1]

Aplicaciones en enrutamiento

Una variante distribuida del algoritmo Bellman-Ford se utiliza en protocolos de enrutamiento por vector de distancia , por ejemplo, el Protocolo de información de enrutamiento (RIP). El algoritmo es distribuido porque involucra una cantidad de nodos (enrutadores) dentro de un sistema autónomo (AS) , una colección de redes IP que normalmente son propiedad de un ISP. Consta de los siguientes pasos:

1. Cada nodo calcula las distancias entre él mismo y todos los demás nodos dentro del AS y almacena esta información como una tabla.
2. Cada nodo envía su tabla a todos los nodos vecinos.
3. Cuando un nodo recibe tablas de distancia 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 Bellman-Ford en este contexto son las siguientes:

• No escala bien.
• Los cambios en la topología de la red no se reflejan rápidamente ya que las actualizaciones se distribuyen nodo por nodo.
• Cuente hasta el infinito si las fallas de un enlace o de un nodo hacen que un nodo sea inalcanzable desde algún conjunto de otros nodos; esos nodos pueden pasar una eternidad aumentando gradualmente sus estimaciones de la distancia hasta él y, mientras tanto, puede haber bucles de enrutamiento.

Mejoras

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 finaliza sin realizar ningún cambio, el algoritmo puede finalizarse inmediatamente, ya que las iteraciones posteriores no realizarán más cambios. Con esta condición de finalización temprana, el bucle principal puede, en algunos casos, utilizar muchas menos de | V | − 1 iteraciones, aunque el peor caso del algoritmo permanezca inalterado. Las siguientes mejoras mantienen la complejidad temporal del peor caso. ${\displaystyle O(|V|\cdot |E|)}$

Una variación del algoritmo Bellman-Ford descrito por Moore (1959) reduce el número de pasos de relajación que se deben realizar en 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 las aristas que salen de v , entonces no hay necesidad de relajar las aristas que salen de v una segunda vez. De esta manera, a medida que aumenta el número de vértices con valores de distancia correctos, se reduce el número de aristas salientes que se deben relajar en cada iteración, lo que genera un ahorro de tiempo de factor constante para grafos densos . Esta variación se puede implementar manteniendo una colección de vértices cuyas aristas salientes se deben relajar, eliminando un vértice de esta colección cuando sus aristas se relajan 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 más rápido". ^[6]

Yen (1970) describió otra mejora del algoritmo 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 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 desde E _f y una desde 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 . ^{[7] [8]} ${\displaystyle |V|/2}$

Otra mejora, de 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 sea muy improbable que ocurra el peor caso para la mejora de Yen (en el que los bordes de un camino más corto se alternan estrictamente entre los dos subconjuntos E _f y E _b ). Con un ordenamiento de vértices permutado aleatoriamente, el número esperado de iteraciones necesarias en el bucle principal es como máximo . ^[8] ${\displaystyle |V|/3}$

Notas

1. Bang-Jensen y Gutin (2000)
2. Lección 14 stanford.edu
3. Escritor (2005)
4. Sedgewick (2002).
5. Kleinberg y Tardos (2006).
6. Duan, Fanding (1994). "关于最短路径的SPFA快速算法 [Acerca del algoritmo SPFA]". Revista de la Universidad Southwest Jiaotong . 29 (2): 207–212.
7. Cormen et al., 4ª ed., Problema 22-1, p. 640.
8. Véase los ejercicios web de Sedgewick para algoritmos , 4.ª ed., ejercicios 5 y 12 (consultado el 30 de enero de 2013).

Referencias

Fuentes originales

• Shimbel, A. (1955). Estructura en redes de comunicación . Actas del Simposio sobre redes de información. Nueva York, Nueva York: Polytechnic Press del Instituto Politécnico de Brooklyn. pp. 199–203.
• Bellman, Richard (1958). "Sobre un problema de enrutamiento". Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090/qam/102435 . MR  0102435.
• Ford, Lester R. Jr. (14 de agosto de 1956). Teoría del flujo de redes. Documento P-923. Santa Mónica, California: RAND Corporation.
• Moore, Edward F. (1959). El camino más corto a través de un laberinto . Proc. Internat. Sympos. Switching Theory 1957, Parte II. Cambridge, Massachusetts: Harvard Univ. Press. págs. 285–292. MR  0114710.
• Yen, Jin Y. (1970). "Un algoritmo para encontrar las rutas más cortas desde todos los nodos de origen hasta un destino determinado en redes generales". Quarterly of Applied Mathematics . 27 (4): 526–530. doi : 10.1090/qam/253822 . MR  0253822.
• Bannister, MJ; Eppstein, D. (2012). Aceleración aleatoria del algoritmo Bellman–Ford . Analytic Algorithmics and Combinatorics (ANALCO12), Kioto, Japón. págs. 41–47. arXiv : 1111.5414 . doi :10.1137/1.9781611973020.6.

Fuentes secundarias

• Ford, LR Jr. ; Fulkerson, DR (1962). "Un algoritmo de cadena más corta". Flujos en redes . Princeton University Press. págs. 130–134.
• Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Sección 2.3.4: El algoritmo Bellman-Ford-Moore". Digraphs: Theory, Algorithms and Applications (Primera edición). Springer. ISBN 978-1-84800-997-4.
• Schrijver, Alexander (2005). "Sobre la historia de la optimización combinatoria (hasta 1960)" (PDF) . Manual de optimización discreta . Elsevier: 1–68.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. Introducción a los algoritmos . MIT Press y McGraw-Hill., Cuarta edición. MIT Press, 2022. ISBN 978-0-262-04630-5 . Sección 22.1: El algoritmo Bellman–Ford, págs. 612–616. Problema 22–1, pág. 640. 
• Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "Capítulo 6: Algoritmos de grafos". Algoritmos en pocas palabras . O'Reilly Media . págs. 160–164. ISBN 978-0-596-51624-6.
• Kleinberg, Jon ; Tardos, Éva (2006). Diseño de algoritmos . Nueva York: Pearson Education, Inc.
• Sedgewick, Robert (2002). "Sección 21.7: Pesos de aristas negativas". Algoritmos en Java (3.ª ed.). ISBN 0-201-36121-3Archivado desde el original el 31 de mayo de 2008. Consultado el 28 de mayo de 2007 .