Algoritmo de Bellman-Ford

Ajustar Compartir Imprimir Citar

Algoritmo para encontrar los caminos más cortos en gráficos

El algoritmo Bellman-Ford es un algoritmo que calcula las rutas más cortas desde un único vértice de origen hasta todos los demás vértices en un dígrafo ponderado. 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. El algoritmo fue propuesto por primera vez por Alfonso Shimbel (1955), pero en cambio lleva el nombre de Richard Bellman y Lester Ford Jr., quienes lo publicaron en 1958 y 1956, respectivamente. 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.

Los pesos de borde negativos se encuentran en varias aplicaciones de gráficos, de ahí la utilidad de este algoritmo. Si un gráfico contiene un "ciclo negativo" (es decir, un ciclo cuyas aristas suman un valor negativo) que es accesible desde la fuente, entonces no hay una ruta más barata: cualquier ruta que tenga un punto en el ciclo negativo puede abaratarse en uno más caminar alrededor del ciclo negativo. En tal caso, el algoritmo Bellman-Ford puede detectar e informar el ciclo negativo.

Algoritmo

En este gráfico de ejemplo, asumiendo que A es la fuente y los bordes se procesan en el peor orden, de derecha a izquierda, requiere todo

Silencio V tención1 -

o 4 iteraciones para que las estimaciones de distancia convergen. Por el contrario, si los bordes se procesan en el mejor orden, de izquierda a derecha, el algoritmo converge en una sola iteración.

Como el algoritmo de Dijkstra, Bellman-Ford procede por la relajación, en la que las aproximaciones a la distancia correcta son reemplazadas por mejores hasta que finalmente lleguen a la solución. En ambos algoritmos, la distancia aproximada a cada vértice es siempre una sobreestimación de la verdadera distancia, y es reemplazada por el mínimo de su antiguo valor y la longitud de un camino recién encontrado. Sin embargo, el algoritmo de Dijkstra utiliza una cola prioritaria para seleccionar codicioso 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 $|V|-1$ veces, donde $|V|$ es el número de vértices en el gráfico. En cada una de estas repeticiones, crece el número de vértices con distancias calculadas correctamente, de las cuales sigue que eventualmente 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 insumos que Dijkstra. Las respuestas intermedias dependen del orden de los bordes relajados, pero la respuesta final sigue siendo la misma.

Bellman-Ford corre dentro $O(|V|cdot |E|)$ tiempo, donde $|V|$ y $|E|$ son el número de vértices y bordes respectivamente.

función BellmanFordlista vertices, lista bordes, vertex fuente) es // Esta aplicación lleva en un gráfico, representado como // listas de vértices (representados como enteros [0.n-1]) y bordes, // y llena dos arrays (distance and predecessor) holding // el camino más corto de la fuente a cada vérticedistancia:= lista de tamaño npredecesor:= lista de tamaño n // Paso 1: inicializar el gráfico para cada uno v dentro vertices dodistancia[v]:= inf // Iniciar la distancia a todos los vértices al infinito
predecesor[v]:= nulo // Y tener un antecesor nulo

distancia[fuente]:= 0 // La distancia de la fuente a sí misma es, por supuesto, cero

 // Paso 2: Relaje los bordes repetidamente repetición TENIBIENTES - 1 veces:
 para cada uno (u, v) con peso w dentro bordes do si distancia[u] + w > distancia[v] entoncesdistancia[v]:= distancia[u] + w
predecesor[v]:= u

 // Paso 3: comprobar los ciclos de peso negativo para cada uno v dentro vertices dou:= predecesor[v]
 si u no nulo distancia[u] + peso de (u, v) entonces // Existe un ciclo negativovisitados:= lista de tamaño n inicializado con falsovisitado[v]:= verdadero mientras no visitado[u] dovisitado[u]:= verdaderou:= predecesor[u]
 // u es un vértice en un ciclo negativo, encontrar el ciclo en síncycle:= [u]
v:= predecesor[u]
 mientras v!= u doncycle:= concatenate([v], ncycle)
v:= predecesor[v]
 error "Graph contiene un ciclo de peso negativo", ncycle
 retorno distancia, 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 al destino se puede acortar tomando el borde, la distancia se actualiza al nuevo valor más bajo.

El núcleo del algoritmo es un bucle que explora todos los bordes en cada bucle. Por todos ${displaystyle ileq |V|-1}$ , al final del $i$ -la iteración, de cualquier vértice $v$ , siguiendo el rastro de predecesor grabado en $predecesor$ produce un camino que tiene un peso total que es a la mayoría $distancia[v]$ , y más adelante, $distancia[v]$ es un límite inferior a la longitud de cualquier camino de origen a $v$ que utiliza como máximo $i$ bordes.

Desde el camino más largo posible sin un ciclo puede ser $|V|-1$ bordes, los bordes deben ser escaneados $|V|-1$ tiempos para asegurar el camino más corto se ha encontrado para todos los nodos. Se realiza un escaneo final de todos los bordes y si se actualiza cualquier distancia, entonces un camino de longitud $|V|$ se han encontrado bordes que sólo pueden ocurrir si al menos un ciclo negativo existe en el gráfico.

Prueba de corrección

La corrección del algoritmo se puede demostrar por inducción:

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

si Distanciau) no es infinito, es igual a la longitud de algún camino desde s a u; y
si hay un camino desde s a u con i bordes, entonces Distancia (u) es a la mayoría de la longitud del camino más corto desde s a u con i bordes.

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

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

Para la segunda parte, considere una ruta más corta P (puede haber más de una) desde fuente a v con como máximo i. Sea u el último vértice antes de v en este camino. Entonces, la parte de la ruta desde fuente a u es la ruta más corta desde fuente a u con como máximo bordes i-1, ya que si no fuera así, entonces debe haber un camino estrictamente más corto desde fuente a u con como máximo aristas i-1, y luego podríamos añadir la arista uv a esta ruta para obtener una ruta con como máximo aristas i que sea estrictamente más corta que P—una contradicción. Por suposición inductiva, u.distance después de i−1 iteraciones es como máximo la longitud de esta ruta desde source a u. Por lo tanto, uv.weight + u.distance es como máximo la longitud de P. En la iteración i^th, v.distance se compara con uv.weight + u.distance, y es establezca igual si uv.weight + u.distance es menor. Por lo tanto, después de i iteraciones, v.distance es como máximo la longitud de P, es decir, la longitud de la ruta más corta desde fuente a v que utiliza como máximo los bordes i.

Si no hay ciclos de peso negativo, 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. Por el contrario, suponga que no se puede hacer ninguna mejora. Entonces para cualquier ciclo con vértices v[0],..., v[k−1],

v[i].distancia <= v[i-1 (mod k)].distancia + v[i-1 (mod k)]v[i].peso

Resumiendo alrededor del ciclo, la v[i].distancia y v[i−1 (mod k)].distance términos cancelar, dejando

0 <= suma de 1 a k de v[i-1 (mod k)]v[i].peso

Es decir, cada ciclo tiene un peso no negativo.

Encontrar ciclos negativos

Cuando el algoritmo se usa para encontrar las 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 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 ciclo en análisis de flujo de red.

Aplicaciones en enrutamiento

Una variante distribuida del algoritmo Bellman-Ford se utiliza en los protocolos de enrutamiento de 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 (AS), una colección de redes IP que normalmente son propiedad de un ISP. Consta de los siguientes pasos:

Cada nodo calcula las distancias entre sí y todos los demás nodos dentro de la AS y almacena esta información como tabla.
Cada nodo envía su mesa a todos los nodos vecinos.
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 esta configuración 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 con la infinidad si los fallos de enlace o nodos hacen que un nodo sea inalcanzable de algunos otros nodos, esos nodos pueden pasar por siempre aumentando gradualmente sus estimaciones de la distancia con ella, y mientras tanto puede haber bucles de enrutamiento.

Mejoras

El algoritmo Bellman-Ford puede ser mejorado en la práctica (aunque no en el peor caso) por la observación de que, si una iteración del bucle principal del algoritmo termina sin hacer ningún cambio, el algoritmo se puede terminar inmediatamente, ya que las iteraciones posteriores no harán más cambios. Con esta condición de terminación temprana, el bucle principal puede en algunos casos utilizar muchos menos que $Silencio V TENIDO - 1$ iteraciones, aunque el peor caso del algoritmo permanece sin cambios. Las siguientes mejoras mantienen $O(|V|cdot |E|)$ la peor complejidad del tiempo.

Una variación del algoritmo de Bellman-Ford conocida como algoritmo más rápido de la ruta más corta, descrita por primera vez por Moore (1959), reduce la cantidad de pasos de relajación que deben realizarse 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 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, se reduce el número de vértices cuyos bordes salientes deben relajarse en cada iteración, lo que lleva a un ahorro de tiempo de factor constante para gráficos densos.

Yen (1970) describió otra mejora para el algoritmo Bellman-Ford. Su mejora 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. i. j; el segundo, E_b, contiene bordes (v_i, v_j. i ■ j. Cada vértice se visita en el orden $v 1, v 2,... v Silencio V Silencio$ , relajante cada borde saliente de ese vértice en E_f. Cada vértice se visita entonces en el orden $v Silencio V Silencio, v Silencio V tención1 -,... v 1$ , relajante cada borde saliente de ese vértice en E_b. Cada iteración del bucle principal del algoritmo, después de la primera, añade al menos dos bordes al conjunto de bordes cuyas distancias relajadas coinciden con las distancias más cortas correctas: una desde E_f y uno de E_b. Esta modificación reduce el peor número de iteraciones del bucle principal del algoritmo $Silencio V TENIDO - 1$ a $|V|/2$ .

Otra mejora, por Bannister & Eppstein (2012), sustituye el orden lineal arbitrario de los vértices utilizados en la segunda mejora de Yen por una permutación aleatoria. Este cambio hace el peor caso para la mejora de Yen (en la que los bordes de un camino más corto se alternan estrictamente entre los dos subconjuntos E_f y E_b) muy poco probable que suceda. Con un orden de vértice permutado aleatoriamente, el número esperado de iteraciones necesarias en el bucle principal es en la mayoría $|V|/3$ .