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 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. [2] 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]
Clase | Problema de ruta más corta de fuente única (para gráficos dirigidos ponderados) |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | |
Complejidad espacial en el peor de los casos |
Los pesos de los bordes 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 ciclo cuyos bordes 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 ser abaratado por un paseo más alrededor del ciclo negativo. En tal caso, el algoritmo Bellman-Ford puede detectar y reportar el ciclo negativo. [1] [4]
Algoritmo
Al igual que el algoritmo de Dijkstra , Bellman-Ford procede por relajación , en la que las aproximaciones a la distancia correcta se reemplazan por otras 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 anterior y la longitud de una ruta recién encontrada. Sin embargo, el algoritmo de Dijkstra usa 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 tiempos, donde es 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 Bellman-Ford a una clase más amplia de entradas que Dijkstra.
Bellman – Ford entra tiempo , donde y son el número de vértices y aristas respectivamente.
función BellmanFord ( lista de vértices, lista de bordes, fuente de vértice ) es // Esta implementación toma un grafo, representado como // listas de vértices (representados como enteros [0..n-1]) y bordes, // y llena dos arreglos (distancia y predecesor) que contienen // la ruta más corta desde la fuente de 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 do distancia [v]: = inf // Inicializar la distancia a todos los vértices hasta el infinito predecesor [v]: = null // Y tener un predecesor nulo distancia [fuente]: = 0 // La distancia desde la fuente a sí misma es, por supuesto, cero // 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] + wentonces distancia [v]: = distancia [u] + w predecesor [v]: = u // Paso 3: verificación para los ciclos de peso negativo para cada borde (u, v) con peso w en bordes hacen si distancia [u] + w entonces error "Graph contiene un ciclo de peso negativo" distancia de retorno , predecesor
En pocas palabras, el algoritmo inicializa la distancia a la fuente en 0 y todos los demás nodos en el 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 en la que se escanean los bordes, el algoritmo encuentra todos los caminos más cortos con una longitud máxima de i bordes (y posiblemente algunos caminos más largos que i bordes). Dado que el camino más largo posible sin ciclo puede ser bordes, los bordes deben escanearse 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, entonces una ruta de longitud Se han encontrado bordes que solo pueden ocurrir si existe al menos un ciclo negativo 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 de por bucle,
- Si la distancia ( u ) no es infinito, es igual a la longitud de algún camino de s a u ; y
- si hay un camino de s a u con en la mayoría de i bordes, entonces Distancia (u) es como máximo la longitud de la ruta más corta desde s a u con un máximo de i bordes.
Prueba . Para el caso base de inducción, considere i=0
y el momento antes de que el bucle for se ejecute por primera vez. Luego, para el vértice fuente source.distance = 0
, que es correcto. Para otros vértices u , lo cual también es correcto porque no hay una ruta desde la fuente hasta u con 0 aristas.u.distance = infinity
Para el caso inductivo, primero probamos la primera parte. Considere 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.distance
es la longitud de algún camino desde la fuente hasta u . Entonces u.distance + uv.weight
es la longitud de la ruta desde la fuente hasta v que sigue la ruta 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 un máximo de i bordes. Sea u el último vértice antes de v en este camino. Entonces, la parte de la ruta desde la fuente hasta u es la ruta más corta desde la fuente hasta u con como máximo i-1 aristas, ya que si no lo fuera, entonces debe haber una ruta estrictamente más corta desde la fuente hasta u con como máximo i- 1 bordes, y luego podríamos agregar el borde uv a este camino para obtener un camino con como máximo i bordes que sea estrictamente más corto 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 la fuente hasta u . Por lo tanto, uv.weight + u.distance
es como máximo la longitud de P . En la i- ésima iteración, v.distance
se compara con uv.weight + u.distance
y se iguala si uv.weight + u.distance
es más pequeño. Por lo tanto, después de i iteraciones, v.distance
es 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 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, suponga 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 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 a buscar, por ejemplo, en técnicas de cancelación de ciclo 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 se distribuye porque involucra una cantidad de nodos (enrutadores) dentro de un sistema autónomo (AS) , una colección de redes IP que generalmente son propiedad de un ISP. Consta de los siguientes pasos:
- Cada nodo calcula las distancias entre él y todos los demás nodos dentro del AS y almacena esta información como una tabla.
- Cada nodo envía su tabla 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 hasta el infinito si las fallas de enlace o nodo hacen que un nodo sea inaccesible 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 termina sin realizar ningún cambio, el algoritmo se puede terminar 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 iteraciones, aunque el peor caso del algoritmo permanece sin cambios. Todas las siguientes mejoras mantienen el complejidad de tiempo en el peor de los casos.
Una variación del algoritmo Bellman-Ford conocida como Shortest Path Faster Algorithm , descrita por primera vez 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 las aristas de v , entonces no es necesario relajar las aristas 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 que necesitan ser relajados en cada iteración se reduce, lo que lleva a un ahorro de tiempo de factor constante para gráficos densos .
Yen (1970) describió otra mejora del 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 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 1 , v 2 , ..., v | V | , relajando cada borde saliente de ese vértice en E f . A continuación, 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 bordes al conjunto de bordes cuyas distancias relajadas coinciden con las distancias de trayectoria más cortas correctas: uno desde E f y otro 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. [5] [6]
Otra mejora, de Bannister y 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 sea muy poco probable que ocurra el peor de los casos para la mejora del Yen (en el que los bordes de una ruta más corta se alternan estrictamente entre los dos subconjuntos E f y E b ). Con una ordenación de vértices permutada aleatoriamente, el número esperado de iteraciones necesarias en el bucle principal es como máximo. [6]
Notas
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. págs. 199–203.
- Bellman, Richard (1958). "En un problema de enrutamiento" . Trimestral de Matemática Aplicada . 16 : 87–90. doi : 10.1090 / qam / 102435 . Señor 0102435 .
- Ford, Lester R. Jr. (14 de agosto de 1956). Teoría del flujo de red . Papel 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. Simpos. Switching Theory 1957, Parte II. Cambridge, Massachusetts: Universidad de Harvard. Prensa. págs. 285-292. Señor 0114710 .
- Yen, Jin Y. (1970). "Un algoritmo para encontrar las rutas más cortas desde todos los nodos de origen a un destino determinado en redes generales" . Trimestral de Matemática Aplicada . 27 (4): 526–530. doi : 10.1090 / qam / 253822 . Señor 0253822 .
- Bannister, MJ; Eppstein, D. (2012). Aceleración aleatoria del algoritmo Bellman-Ford . Algoritmia analítica y combinatoria (ANALCO12), Kyoto, Japón. págs. 41–47. arXiv : 1111.5414 . doi : 10.1137 / 1.9781611973020.6 .
Fuentes secundarias
- Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Sección 2.3.4: El algoritmo Bellman-Ford-Moore". Dígrafos: teoría, algoritmos y aplicaciones (Primera ed.). 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., Segunda edicion. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 24.1: El algoritmo de Bellman-Ford, págs. 588–592. Problema 24-1, págs. 614–615. Tercera edicion. Prensa del MIT, 2009. ISBN 978-0-262-53305-8 . Sección 24.1: El algoritmo de Bellman-Ford, págs. 651–655.
- Heineman, George T .; Pollice, Gary; Selkow, Stanley (2008). "Capítulo 6: Algoritmos de gráficos". 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 los bordes negativos". Algoritmos en Java (3ª ed.). ISBN 0-201-36121-3. Archivado desde el original el 31 de mayo de 2008 . Consultado el 28 de mayo de 2007 .