LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El algoritmo de Bellman-Ford es un algoritmo que calcula las rutas más cortas desde un vértice de una sola fuente a todos los otros 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 borde son números negativos. 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. ^[2] Edward F. Mooretambién publicó el mismo algoritmo en 1957, y por esta razón a veces también se le llama el algoritmo de Bellman-Ford-Moore . ^[1]

Los pesos de borde negativos se encuentran en varias aplicaciones de gráficos, de ahí la utilidad de este algoritmo. ^[3] Si un gráfico contiene un "ciclo negativo" (es decir, un ciclocuyos bordes se suman a un valor negativo) al que se puede acceder desde la fuente, entonces no hay una ruta más barata : cualquier ruta que tenga un punto en el ciclo negativo puede ser Hecho más barato por un paseo más alrededor del ciclo negativo. En tal caso, el algoritmo de Bellman-Ford puede detectar e informar el ciclo negativo. 

Algoritmo de Bellman-Ford

Clase	Problema de la ruta más corta de una sola fuente (para gráficos dirigidos ponderados)
Estructura de datos	Grafico
Peor desempeño	$${\ displaystyle \ Theta (| V || E |)}
El mejor rendimiento del caso	$${\ displaystyle \ Theta (| E |)}
La peor complejidad del espacio	$${\ displaystyle \ Theta (| V |)}

Algoritmo [ editar ]

En este gráfico de ejemplo, suponiendo que A es la fuente y los bordes se procesan en el peor orden, de derecha a izquierda, se requiere la totalidad | V | −1 o 4 iteraciones 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 , Bellman-Ford procede por relajación , en la cual las aproximaciones a la distancia correcta se reemplazan por mejores hasta que finalmente llegan a la solución. En ambos algoritmos, la distancia aproximada a cada vértice es siempre una sobreestimación de la distancia real, y se reemplaza por el mínimo de su valor antiguo y la longitud de una ruta recientemente encontrada. 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 se ha 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 la gráfica. En cada una de estas repeticiones, el número de vértices con distancias calculadas correctamente crece, de lo que se deduce que, eventualmente, todos los vértices tendrán sus distancias correctas. Este método permite que el algoritmo de Bellman-Ford se aplique a una clase de entradas más amplia que Dijkstra.

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 bordes, fuente de vértice )
   :: distancia [], predecesor []
   
   // Esta implementación toma un gráfico, representado como 
   // listas de vértices y bordes, y llena dos matrices 
   // (distancia y predecesor) sobre la ruta más corta 
   // desde la fuente a cada vértice
   
   // Paso 1: inicializar el gráfico 
   para cada vértice v en vértices:
       distancia [v]: = inf              // Inicializa la distancia a todos los vértices hasta el infinito
       predecesor [v]: = null          // Y tiene un predecesor nulo
   
   distancia [fuente]: = 0 // La distancia desde la fuente a sí misma es, por supuesto, cero
   
   // Paso 2: relaje los bordes repetidamente 
   para i desde 1 hasta tamaño (vértices) -1:
        para cada borde (u, v) con peso w en los bordes:
            si distancia [u] + w 
               distancia [v]: = distancia [u] + w
               predecesor [v]: = u
   
   // Paso 3: compruebe los ciclos de peso negativo 
   para cada borde (u, v) con peso w en los bordes:
        si distancia [u] + w error "El gráfico contiene un ciclo de peso negativo"
   
   distancia de retorno [], predecesor []

En pocas palabras, el algoritmo inicializa la distancia a la fuente a 0 y todos los demás nodos al infinito. Luego, para todos los bordes, si la distancia al destino se puede acortar tomando el borde, la distancia se actualiza al nuevo valor más bajo. En cada iteración i que se escanean los bordes, el algoritmo encuentra todas las rutas más cortas de los bordes i más largos (y posiblemente algunas rutas más largas que los bordes i ). Dado que el camino más largo posible sin un ciclo puede ser$${\ displaystyle | V | -1} bordes, los bordes deben ser escaneados $${\ displaystyle | V | -1}tiempos para asegurar 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 cualquier distancia, se realiza un recorrido de longitud.$${\ displaystyle | V |} Se han encontrado bordes que solo pueden ocurrir si existe al menos un ciclo negativo en el gráfico.

Prueba de corrección [ editar ]

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material sin fuente puede ser cuestionado y eliminado . ( Marzo de 2019 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

La exactitud del algoritmo se puede mostrar por inducción :

Lema . Después de las repeticiones de i para bucle,

• si la Distancia ( u ) no es infinita, es igual a la longitud de algún camino desde s hasta u ; y
• si hay una ruta desde s hasta u con un máximo de i bordes, entonces Distancia (u) es como máximo la longitud del camino más corto desde s hasta u con un máximo de i bordes.

Prueba . Para el caso base de inducción, considere i=0y el momento anterior al bucle for se ejecuta por primera vez. Luego, para el vértice fuente source.distance = 0, que es correcto. Para otros vértices u , , que también es correcto porque no hay un camino desde la fuente de u con 0 bordes. u.distance = infinity

Para el caso inductivo, primero probamos la primera parte. Considere un momento en que la distancia de un vértice se actualiza por v.distance := u.distance + uv.weight. Por suposición inductiva, u.distancees la longitud de algún camino desde la fuente hasta u . Luego u.distance + uv.weightes la longitud de la ruta de la fuente a la v que sigue la ruta de la fuente a la u y luego va a la v .

Para la segunda parte, considere una ruta más corta P (puede haber más de una) desde la fuente hasta la u con un máximo de i bordes. Sea v el último vértice antes de u en este camino. Entonces, la parte de la ruta desde la fuente a v es la ruta más corta desde la fuente a la v con un máximo de i-1 bordes, ya que si no lo fuera, entonces debe haber una ruta estrictamente más corta desde la fuente a la v con la mayor i - 1 bordes, y luego podríamos añadir el borde uv a este camino para obtener un camino con un máximo deLos bordes son estrictamente más cortos que P, una contradicción. Por suposición inductiva, v.distancedespués de i −1, las iteraciones tienen como máximo la longitud de esta ruta desde la fuente a la v . Por lo tanto, uv.weight + v.distancees como máximo la longitud de P . En el i ^ª iteración, u.distanceobtiene en comparación con uv.weight + v.distance, y se fija igual a él si uv.weight + v.distancees menor. Por lo tanto, después de i iteraciones, u.distancees como máximo la longitud de P , es decir, la longitud de la ruta más corta desde la fuente de u que utiliza en la mayoría de i bordes.

Si no hay ciclos de peso negativo, entonces cada ruta más corta visita cada vértice como máximo una vez, por lo que en el paso 3 no se pueden realizar más mejoras. A la inversa, 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, v [ i ] .distance y v [ i −1 (mod k )]. Los términos de 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.

Encontrando ciclos negativos [ editar ]

Cuando el algoritmo se usa para encontrar rutas más cortas, la existencia de ciclos negativos es un problema, lo 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 usar para aplicaciones en las que este es el objetivo que debe buscarse, por ejemplo, en técnicas de cancelación de ciclos en el análisis de flujo de red . ^[1]

Aplicaciones en enrutamiento [ editar ]

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

1. Cada nodo calcula las distancias entre sí 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 de Bellman-Ford en esta configuración son las siguientes:

• No se 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 del enlace o del nodo hacen que un nodo sea inalcanzable de algún conjunto de otros nodos, esos nodos pueden gastar para siempre incrementando gradualmente sus estimaciones de la distancia hasta él, y mientras tanto puede haber bucles de enrutamiento.

Mejoras [ editar ]

El algoritmo de 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 subsiguientes No hagas más cambios. Con esta condición de terminación temprana, el bucle principal puede, en algunos casos, usar muchos menos que | V | - 1 iteraciones, aunque el peor de los casos del algoritmo permanece sin cambios.

Yen (1970) describió dos mejoras más al algoritmo de Bellman-Ford para una gráfica sin ciclos de peso negativo; de nuevo, mientras hacen el algoritmo más rápido en la práctica, no cambian su$${\ displaystyle O (| V | \ cdot | E |)}El peor de los casos es el tiempo límite. Su primera mejora 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 es necesario relajar los bordes de v una segunda vez. De esta manera, a medida que aumenta el número de vértices con valores de distancia correctos, el número cuyos bordes salientes que deben relajarse en cada iteración se reduce, lo que lleva a un factor de ahorro constante en el tiempo para los gráficos densos .

La segunda mejora de Yen primero asigna un orden lineal arbitrario en todos los vértices y luego divide el conjunto de todos los bordes en dos subconjuntos. El primer subconjunto, E _f , contiene todos los bordes ( v _i , v _j) de manera que i < j ; el segundo, E _b , contiene bordes ( v _i , v _j ) de manera que i > j . Cada vértice se visita en el orden v ₁ , v ₂ , ..., v _| V |, relajando cada borde saliente de ese vértice en E _f . Cada vértice se visita en el orden v _| V | , v _{| V | −1} , ..., v ₁ , relajando cada borde saliente de ese vértice en E _b . Cada iteración del bucle principal del algoritmo, después del primero, agrega al menos dos bordes al conjunto de bordes cuyas distancias relajadas coinciden con las distancias de ruta más cortas correctas: 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 desde | V| - 1 a$${\ displaystyle | V | / 2}. ^[5] [6]

Otra mejora, por Bannister & Eppstein (2012) , reemplaza el orden lineal arbitrario de los vértices utilizados 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 los bordes de una ruta más corta estrictamente alternados entre los dos subconjuntos E _f y E _b ) sea muy improbable. Con un orden de vértices permutado al azar, el número esperado de iteraciones necesarias en el bucle principal es como máximo$${\ displaystyle | V | / 3}. ^[6]

En China, un algoritmo que agrega una cola de primero en entrar, primero en salir, al algoritmo Bellman-Ford, conocido como SPFA , publicado por Fanding Duan en 1994, es popular entre los estudiantes que participan en NOIP y ACM-ICPC .