El algoritmo de Bellman-Ford explicado

Mohammed Islam Hadjoudj

Ingeniero experto en investigación de operaciones

1. Introducción al algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford es uno de los algoritmos más fundamentales de la teoría de grafos. Bautizado en honor a sus pioneros, Richard Bellman y Lester Ford Jr., que lo publicaron a finales de la década de 1950, este algoritmo resuelve el problema del camino más corto de origen único. Es decir, encuentra el camino más corto desde un nodo de partida hasta todos los demás nodos de un grafo ponderado.

Si conoces el algoritmo de Dijkstra, quizá te preguntes: "¿Por qué necesitamos otro algoritmo para exactamente el mismo problema?". La respuesta está en la versatilidad. Aunque el algoritmo de Dijkstra es más rápido y muy eficiente en grafos donde todos los pesos de las aristas son positivos (como las redes de carreteras físicas), se viene abajo por completo cuando aparecen pesos de arista negativos. Bellman-Ford, en cambio, admite los pesos negativos y ofrece un mecanismo robusto para manejarlos, garantizando cálculos precisos del camino más corto incluso en escenarios económicos o de red complejos.

Además, Bellman-Ford tiene un superpoder único: puede detectar ciclos negativos. Un ciclo negativo es un bucle en un grafo donde la suma de los pesos de las aristas es menor que cero. Si existe tal ciclo, el concepto de "camino más corto" pierde sentido, porque en teoría se podría recorrer el ciclo infinitamente para lograr una longitud de camino de menos infinito. Bellman-Ford detecta esta anomalía y te avisa de ella, lo que lo convierte en una herramienta indispensable para la detección de anomalías en diversos campos, incluido el arbitraje financiero.

2. El problema de Dijkstra: pesos negativos

Para apreciar de verdad la necesidad del algoritmo de Bellman-Ford, primero debemos examinar la limitación crítica del algoritmo de Dijkstra.

El algoritmo de Dijkstra funciona con un principio voraz. Mantiene un conjunto de nodos no visitados y, en cada paso, elige el nodo con la menor distancia conocida desde el origen. Una vez seleccionado un nodo, Dijkstra considera su distancia más corta como "definitiva" y nunca vuelve a visitarlo para actualizar su distancia. Esta suposición funciona a la perfección cuando todos los pesos de las aristas son positivos, porque añadir otra arista a un camino siempre aumenta la longitud total. Por lo tanto, ningún camino descubierto después podría ser más corto que el ya definitivo.

¿Pero qué ocurre cuando introducimos un peso de arista negativo?

Considera un grafo simple con tres nodos: A, B y C. El nodo de partida es A.

• La arista de A a B tiene un peso de 5.
• La arista de A a C tiene un peso de 10.
• La arista de B a C tiene un peso de -8.

Si ejecutamos el algoritmo de Dijkstra desde A, primero explorará los vecinos B (distancia 5) y C (distancia 10). El siguiente nodo en definirse es B, porque 5 es menor que 10. La distancia más corta a B queda fijada en 5. A continuación, examina las aristas desde B. Ve la arista de B a C con peso -8. El nuevo camino a C es A -> B -> C, con un peso total de 5 + (-8) = -3. Pero el algoritmo de Dijkstra es voraz; si hubiera definido C antes de darse cuenta de que había una arista negativa, o si el grafo fuera más complejo, Dijkstra no actualizaría C correctamente y devolvería un resultado incorrecto. En grafos más complejos, la suposición voraz de Dijkstra de que "los caminos más largos no pueden acortarse" se desmorona.

Aquí es donde brilla Bellman-Ford. Abandona el enfoque voraz y, en su lugar, relaja sistemáticamente todas las aristas varias veces, garantizando que, aunque una arista negativa ofrezca un atajo más corto más adelante en el proceso, el algoritmo identifique y actualice correctamente el camino más corto.

3. El peligro de los ciclos negativos

Un ciclo negativo es un bucle cerrado en un grafo donde la suma de los pesos de las aristas que forman el ciclo es menor que cero. Este concepto es fundamental para entender por qué Bellman-Ford está diseñado como está.

Imagina un grafo con los nodos A, B y C formando un triángulo. Los pesos de las aristas son A a B (2), B a C (-5) y C a A (1). El peso total de este ciclo es 2 + (-5) + 1 = -2. Si quieres encontrar el camino más corto de A a cualquier otro sitio, podrías simplemente dar vueltas por este ciclo infinitamente. Cada vez que completas el bucle, tu distancia total disminuye en 2. Tras una vuelta, la distancia es -2; tras diez vueltas, es -20. A medida que te acercas al infinito, el camino más corto se vuelve menos infinito.

En presencia de un ciclo negativo alcanzable desde el nodo de origen, el problema del camino más corto no tiene solución. Los algoritmos estándar quedarían atrapados en un bucle infinito, intentando constantemente encontrar un camino "más corto". Bellman-Ford evita con elegancia este bucle infinito y detecta explícitamente la presencia del ciclo.

4. Concepto central: relajación de aristas

La base del algoritmo de Bellman-Ford es un proceso llamado relajación de aristas. Es el mecanismo por el cual el algoritmo actualiza la menor distancia conocida a un nodo.

Definamos dos arreglos (o diccionarios):

• distance[]: almacena la menor distancia conocida desde el nodo de partida hasta todos los demás. Inicialmente, la distancia al nodo de inicio es 0 y la de todos los demás nodos se fija en infinito (∞).
• predecessor[] (opcional pero útil): almacena el nodo que precede inmediatamente a un nodo dado en el camino más corto. Sirve para reconstruir el camino real una vez que el algoritmo termina.

La operación de relajación para una arista del nodo u al nodo v con peso w se define así:

if distance[u] + w < distance[v]:
    distance[v] = distance[u] + w
    predecessor[v] = u

En lenguaje llano: "Si la distancia conocida al nodo u más el peso de la arista de u a v es menor que la menor distancia conocida al nodo v, ¡hemos encontrado un camino mejor! Actualiza la distancia más corta a v."

El algoritmo de Bellman-Ford simplemente recorre todas las aristas del grafo e intenta relajarlas una y otra vez.

5. Ejecución paso a paso de Bellman-Ford

Ahora, recorramos los pasos exactos del algoritmo.

Sea V el número de vértices (nodos) del grafo y E el número de aristas. El algoritmo se desarrolla en tres fases principales.

Fase 1: Inicialización

Inicializa el arreglo distance. Fija la distancia al nodo de partida en 0 y la de todos los demás nodos en infinito. Esto representa que, al principio, no sabemos cómo llegar a ningún nodo distinto del de inicio.

Fase 2: Relajación repetida

Este es el núcleo del algoritmo. Debemos relajar todas las aristas del grafo, y hacerlo V - 1 veces.

¿Por qué exactamente V - 1 veces? Considera un grafo con V nodos. El camino más corto simple más largo posible (un camino sin ciclos) entre dos nodos cualesquiera puede tener como mucho V - 1 aristas. En el peor de los casos, hace falta una iteración completa sobre todas las aristas para garantizar que los caminos de 1 arista son correctos. Se necesitan dos iteraciones para garantizar los de 2 aristas, y así sucesivamente. Por lo tanto, tras V - 1 iteraciones, si no hay ciclos negativos, tenemos garantizado haber encontrado el camino más corto absoluto a cada nodo, sin importar el orden en que procesemos las aristas.

1. Inicia un bucle que se ejecute V - 1 veces.
2. Dentro de este bucle, recorre cada una de las aristas del grafo.
3. Para cada arista (u, v) con peso w, intenta relajarla: si distance[u] + w < distance[v], actualiza distance[v].

Fase 3: Detección de ciclos negativos

Tras completar la fase 2, tenemos las distancias más cortas, suponiendo que no existen ciclos negativos. Para comprobar si hay ciclos negativos, ejecutamos una iteración final adicional sobre todas las aristas.

1. Recorre una última vez cada arista (u, v) con peso w.
2. Intenta relajarla. Si distance[u] + w < distance[v] SIGUE siendo cierto, significa que hemos encontrado un camino aún más corto después de V - 1 aristas.
3. Esto es matemáticamente imposible para un camino simple. La única explicación es que hemos entrado en un ciclo de peso negativo que permite reducir la distancia infinitamente. Si esto ocurre, el algoritmo termina e informa de que existe un ciclo negativo.

6. Implementación y pseudocódigo

La belleza de Bellman-Ford reside en su sencillez. La implementación es notablemente directa, a menudo solo unos pocos bucles anidados. Aquí tienes el pseudocódigo estándar:

function BellmanFord(Graph, source):
    // Fase 1: Inicialización
    distance = array of size |V|, filled with Infinity
    predecessor = array of size |V|, filled with Null
    distance[source] = 0

    // Fase 2: Relajar todas las aristas |V| - 1 veces
    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in Graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

    // Fase 3: Comprobar ciclos de peso negativo
    for each edge (u, v) with weight w in Graph:
        if distance[u] + w < distance[v]:
            return "Error: el grafo contiene un ciclo de peso negativo"

    return distance, predecessor

Este código es independiente del lenguaje y se traduce con facilidad a Python, C++, Java o JavaScript.

7. Análisis de complejidad temporal y espacial

Aunque Bellman-Ford es muy versátil, conlleva un coste de rendimiento frente a los algoritmos voraces.

• Complejidad temporal: el algoritmo ejecuta un bucle V - 1 veces y, dentro de él, recorre todas las E aristas. Por tanto, la complejidad temporal de la fase 2 es O(V * E). La fase de detección de ciclos cuesta O(E). La complejidad temporal total es O(V * E). En un grafo denso donde E se acerca a V², la complejidad se aproxima a O(V³). Esto lo hace bastante más lento que el algoritmo de Dijkstra, que puede lograr O(V log V + E) con un montículo de Fibonacci.
• Complejidad espacial: el algoritmo solo necesita almacenar el arreglo distance y el arreglo predecessor, ambos de tamaño V. También debe almacenar el propio grafo. Por tanto, la complejidad espacial auxiliar es O(V).

Debido a su complejidad temporal de O(V * E), Bellman-Ford suele usarse solo cuando es necesario, es decir, cuando hay pesos negativos o la detección de ciclos negativos es un requisito estricto. Para grafos estrictamente positivos, Dijkstra es la opción preferida.

8. Aplicaciones reales

A pesar de ser más lento que Dijkstra, Bellman-Ford tiene aplicaciones reales de gran calado, sobre todo en redes y finanzas.

Protocolo de información de enrutamiento (RIP)

En las redes informáticas, los protocolos de enrutamiento determinan cómo viajan los paquetes de datos por internet. Uno de los protocolos más antiguos y famosos, el Protocolo de información de enrutamiento (RIP), es un protocolo de enrutamiento por vector de distancia que se apoya en gran medida en una variante distribuida del algoritmo de Bellman-Ford.

En esta configuración distribuida, los routers no tienen un mapa completo de toda la red. En su lugar, cada router solo conoce a sus vecinos inmediatos. Los routers comparten periódicamente sus tablas de enrutamiento (sus distancias más cortas conocidas a varios destinos) con sus vecinos. Cuando un router recibe una actualización, usa la ecuación de relajación de Bellman-Ford para actualizar su propia tabla. Con el tiempo, esta información se propaga por la red, permitiendo que todos los routers converjan en los caminos más cortos.

Detección de arbitraje financiero

El arbitraje es la práctica de aprovechar una diferencia de precio entre dos o más mercados. En el mercado de divisas (Forex), los tipos de cambio fluctúan. Existe una oportunidad de arbitraje si puedes empezar con una divisa, cambiarla a través de una secuencia de otras divisas y terminar con más de tu divisa original de la que empezaste, sin asumir ningún riesgo de mercado.

Podemos modelar los tipos de cambio como un grafo donde los nodos son divisas (USD, EUR, GBP, etc.) y las aristas representan el tipo de cambio. Como multiplicamos los tipos de cambio en lugar de sumarlos, podemos tomar el logaritmo negativo de los tipos para convertir el problema en uno aditivo. Una oportunidad de arbitraje (donde el producto de los tipos > 1) se transforma en un ciclo negativo en nuestro grafo modificado. Ejecutar Bellman-Ford en este grafo detectará esos ciclos negativos, identificando al instante bucles de arbitraje rentables para los operadores algorítmicos.

9. Recursos académicos e historia

El algoritmo de Bellman-Ford a veces se denomina algoritmo de Bellman-Ford-Moore para reconocer las contribuciones independientes de estos tres científicos de la computación:

• Alfonso Shimbel (1955): propuso originalmente el algoritmo, aunque se popularizó menos.
• Edward F. Moore (1959): publicó una variación del algoritmo en "The shortest path through a maze" (Proceedings of the International Symposium on the Theory of Switching).
• Richard Bellman (1958): lo formalizó en "On a routing problem" (Quarterly of Applied Mathematics).
• Lester Ford Jr. (1956): desarrolló los conceptos fundamentales en "Network Flow Theory" (RAND Corporation Paper).

Este algoritmo sentó las bases de la programación dinámica, un método célebremente iniciado por el propio Richard Bellman, que dio lugar a amplias aplicaciones en las matemáticas, la economía y la informática.