Algoritmo de Bellman-Ford

Caminos más cortos desde una sola fuente con aristas de peso negativo

Supongamos que se nos da un grafo dirigido ponderado $G$ con $n$ vértices y $m$ aristas, y algún vértice especificado $v$ . Queremos encontrar la longitud de los caminos más cortos desde el vértice $v$ hacia todos los demás vértices.

A diferencia del algoritmo de Dijkstra, este algoritmo también se puede aplicar a grafos que contienen aristas de peso negativo. Sin embargo, si el grafo contiene un ciclo negativo, entonces, claramente, el camino más corto hacia algunos vértices puede no existir (debido a que el peso del camino más corto debe ser igual a menos infinito); no obstante, este algoritmo se puede modificar para señalar la presencia de un ciclo de peso negativo, o incluso para reconstruir ese ciclo.

El algoritmo lleva el nombre de dos científicos estadounidenses: Richard Bellman y Lester Ford. Ford inventó este algoritmo en 1956 durante el estudio de otro problema matemático, que eventualmente se redujo a un subproblema de encontrar los caminos más cortos en el grafo, y Ford dio un esbozo del algoritmo para resolver este problema. Bellman en 1958 publicó un artículo dedicado específicamente al problema de encontrar el camino más corto, y en ese artículo formuló con claridad el algoritmo en la forma en que lo conocemos ahora.

Descripción del algoritmo

Asumamos que el grafo no contiene ningún ciclo de peso negativo. El caso de la presencia de un ciclo de peso negativo se discutirá más abajo en una sección aparte.

Crearemos un arreglo de distancias $d[0 \ldots n-1]$ , que después de la ejecución del algoritmo contendrá la respuesta al problema. Al principio lo llenamos de la siguiente manera: $d[v] = 0$ , y todos los demás elementos $d[ ]$ iguales a infinito $\infty$ .

El algoritmo consiste en varias fases. Cada fase recorre todas las aristas del grafo, y el algoritmo intenta producir una relajación (relaxation) a lo largo de cada arista $(a,b)$ de peso $c$ . La relajación a lo largo de las aristas es un intento de mejorar el valor $d[b]$ usando el valor $d[a] + c$ . De hecho, significa que intentamos mejorar la respuesta para este vértice usando la arista $(a,b)$ y la respuesta actual para el vértice $a$ .

Se afirma que $n-1$ fases del algoritmo bastan para calcular correctamente las longitudes de todos los caminos más cortos en el grafo (de nuevo, creemos que no existen ciclos de peso negativo). Para los vértices inalcanzables la distancia $d[ ]$ permanecerá igual a infinito $\infty$ .

Implementación

A diferencia de muchos otros algoritmos sobre grafos, para el algoritmo de Bellman-Ford resulta más conveniente representar el grafo usando una única lista de todas las aristas (en lugar de $n$ listas de aristas — las aristas que salen de cada vértice). Empezamos la implementación con una estructura $\rm edge$ para representar las aristas. La entrada del algoritmo son los números $n$ , $m$ , la lista $e$ de aristas y el vértice de partida $v$ . Todos los vértices están numerados de $0$ a $n - 1$ .

La implementación más simple

La constante $\rm INF$ denota el número “infinito” — hay que elegirla de modo que sea mayor que todas las longitudes de camino posibles.


struct Edge {
    int a, b, cost;
};
 
int n, m, v;
vector<Edge> edges;
const int INF = 1000000000;
 
void solve()
{
    vector<int> d(n, INF);
    d[v] = 0;
    for (int i = 0; i < n - 1; ++i)
        for (Edge e : edges)
            if (d[e.a] < INF)
                d[e.b] = min(d[e.b], d[e.a] + e.cost);
    // mostrar d, por ejemplo, en pantalla
}

La verificación if (d[e.a] < INF) solo hace falta si el grafo contiene aristas de peso negativo: sin esa verificación se relajaría desde vértices hacia los cuales todavía no se encontraron caminos, y aparecerían distancias incorrectas del tipo $\infty - 1$ , $\infty - 2$ , etc.

Una implementación mejor

Este algoritmo se puede acelerar un poco: a menudo ya obtenemos la respuesta en unas pocas fases y en las fases restantes no se hace ningún trabajo útil, solo se pierde tiempo visitando todas las aristas. Entonces, mantengamos una bandera que indique si algo cambió en la fase actual o no, y si en alguna fase no cambió nada, el algoritmo se puede detener. (Esta optimización no mejora el comportamiento asintótico, es decir, algunos grafos seguirán necesitando las $n-1$ fases, pero acelera de forma significativa el comportamiento del algoritmo “en promedio”, es decir, sobre grafos aleatorios.)

Con esta optimización, en general no hace falta restringir manualmente el número de fases del algoritmo a $n-1$ — el algoritmo se detendrá después de la cantidad deseada de fases.


void solve()
{
    vector<int> d(n, INF);
    d[v] = 0;
    for (;;) {
        bool any = false;
 
        for (Edge e : edges)
            if (d[e.a] < INF)
                if (d[e.b] > d[e.a] + e.cost) {
                    d[e.b] = d[e.a] + e.cost;
                    any = true;
                }
 
        if (!any)
            break;
    }
    // mostrar d, por ejemplo, en pantalla
}

Recuperación del camino

Consideremos ahora cómo modificar el algoritmo para que no solo encuentre la longitud de los caminos más cortos, sino que también permita reconstruirlos.

Para eso, creemos otro arreglo $p[0 \ldots n-1]$ , donde para cada vértice guardamos su “predecesor”, es decir, el penúltimo vértice en el camino más corto que lleva hasta él. De hecho, el camino más corto hacia cualquier vértice $a$ es un camino más corto hacia algún vértice $p[a]$ , al cual le agregamos $a$ al final del camino.

Nótese que el algoritmo trabaja con la misma lógica: asume que la distancia más corta hacia un vértice ya está calculada e intenta mejorar la distancia más corta hacia otros vértices desde ese vértice. Por lo tanto, en el momento de la mejora solo hay que recordar $p[ ]$ , es decir, el vértice desde el cual se produjo esta mejora.

A continuación hay una implementación de Bellman-Ford con la recuperación del camino más corto hacia un nodo dado $t$ :


void solve()
{
    vector<int> d(n, INF);
    d[v] = 0;
    vector<int> p(n, -1);
 
    for (;;) {
        bool any = false;
        for (Edge e : edges)
            if (d[e.a] < INF)
                if (d[e.b] > d[e.a] + e.cost) {
                    d[e.b] = d[e.a] + e.cost;
                    p[e.b] = e.a;
                    any = true;
                }
        if (!any)
            break;
    }
 
    if (d[t] == INF)
        cout << "No path from " << v << " to " << t << ".";
    else {
        vector<int> path;
        for (int cur = t; cur != -1; cur = p[cur])
            path.push_back(cur);
        reverse(path.begin(), path.end());
 
        cout << "Path from " << v << " to " << t << ": ";
        for (int u : path)
            cout << u << ' ';
    }
}

Aquí, partiendo del vértice $t$ , recorremos los predecesores hasta llegar al vértice de partida, que no tiene predecesor, y guardamos todos los vértices del camino en la lista $\rm path$ . Esta lista es un camino más corto de $v$ a $t$ , pero en orden inverso, así que llamamos a la función $\rm reverse()$ sobre $\rm path$ y después imprimimos el camino.

Demostración del algoritmo

Primero, nótese que para todos los vértices inalcanzables $u$ el algoritmo funcionará correctamente: la etiqueta $d[u]$ permanecerá igual a infinito (porque el algoritmo de Bellman-Ford encontrará algún camino hacia todos los vértices alcanzables desde el vértice de partida $v$ , y la relajación para todos los demás vértices restantes nunca ocurrirá).

Demostremos ahora la siguiente afirmación: Después de la ejecución de la $i_{th}$ fase, el algoritmo de Bellman-Ford encuentra correctamente todos los caminos más cortos cuyo número de aristas no supera $i$ .

En otras palabras, para cualquier vértice $a$ denotemos por $k$ el número de aristas en el camino más corto hacia él (si hay varios de esos caminos, se puede tomar cualquiera). Según esta afirmación, el algoritmo garantiza que después de la $k_{th}$ fase se habrá encontrado el camino más corto para el vértice $a$ .

Demostración: Consideremos un vértice arbitrario $a$ hacia el cual hay un camino desde el vértice de partida $v$ , y consideremos un camino más corto hacia él $(p_0=v, p_1, \ldots, p_k=a)$ . Antes de la primera fase, el camino más corto hacia el vértice $p_0 = v$ se encontró correctamente. Durante la primera fase, la arista $(p_0,p_1)$ fue revisada por el algoritmo y, por lo tanto, la distancia al vértice $p_1$ se calculó correctamente después de la primera fase. Repitiendo esta afirmación $k$ veces, vemos que después de la $k_{th}$ fase la distancia al vértice $p_k = a$ queda calculada correctamente, que es lo que queríamos demostrar.

Lo último que hay que notar es que cualquier camino más corto no puede tener más de $n - 1$ aristas. Por lo tanto, basta con que el algoritmo llegue hasta la $(n-1)_{th}$ fase. Después de eso, está garantizado que ninguna relajación mejorará la distancia hacia algún vértice.

El caso de un ciclo negativo

En todo lo anterior consideramos que no hay un ciclo negativo en el grafo (más precisamente, nos interesa un ciclo negativo que sea alcanzable desde el vértice de partida $v$ , y, para ciclos inalcanzables, nada de lo anterior cambia). En presencia de uno o más ciclos negativos, hay complicaciones adicionales asociadas al hecho de que las distancias a todos los vértices de ese ciclo, así como las distancias a los vértices alcanzables desde ese ciclo, no están definidas — deberían ser iguales a menos infinito $(- \infty)$ .

Es fácil ver que el algoritmo de Bellman-Ford puede relajar de forma interminable entre todos los vértices de este ciclo y los vértices alcanzables desde él. Por lo tanto, si no se limita el número de fases a $n - 1$ , el algoritmo se ejecutará indefinidamente, mejorando constantemente la distancia desde esos vértices.

De aquí obtenemos el criterio de presencia de un ciclo de pesos negativos alcanzable desde el vértice fuente $v$ : después de la $(n-1)_{th}$ fase, si ejecutamos el algoritmo una fase más y realiza al menos una relajación adicional, entonces el grafo contiene un ciclo de peso negativo alcanzable desde $v$ ; en caso contrario, tal ciclo no existe.

Más aún, si se encuentra tal ciclo, el algoritmo de Bellman-Ford se puede modificar para que recupere este ciclo como una secuencia de los vértices que lo componen. Para esto, basta recordar el último vértice $x$ para el cual hubo una relajación en la $n_{th}$ fase. Este vértice o bien yace sobre un ciclo de peso negativo, o es alcanzable desde él. Para obtener los vértices que está garantizado que yacen sobre un ciclo negativo, partiendo del vértice $x$ , recorremos los predecesores $n$ veces. De este modo, llegaremos al vértice $y$ , que está garantizado que yace sobre un ciclo negativo. Tenemos que partir de este vértice, a través de los predecesores, hasta volver al mismo vértice $y$ (y sucederá, porque las relajaciones en un ciclo de peso negativo ocurren de forma circular).

Implementación:


void solve()
{
    vector<int> d(n, INF);
    d[v] = 0;
    vector<int> p(n, -1);
    int x;
    for (int i = 0; i < n; ++i) {
        x = -1;
        for (Edge e : edges)
            if (d[e.a] < INF)
                if (d[e.b] > d[e.a] + e.cost) {
                    d[e.b] = max(-INF, d[e.a] + e.cost);
                    p[e.b] = e.a;
                    x = e.b;
                }
    }
 
    if (x == -1)
        cout << "No negative cycle from " << v;
    else {
        int y = x;
        for (int i = 0; i < n; ++i)
            y = p[y];
 
        vector<int> path;
        for (int cur = y;; cur = p[cur]) {
            path.push_back(cur);
            if (cur == y && path.size() > 1)
                break;
        }
        reverse(path.begin(), path.end());
 
        cout << "Negative cycle: ";
        for (int u : path)
            cout << u << ' ';
    }
}

Debido a la presencia de un ciclo negativo, en $n$ iteraciones del algoritmo las distancias pueden irse lejos hacia el rango negativo (a números negativos del orden de $-n m W$ , donde $W$ es el valor absoluto máximo de cualquier peso en el grafo). Por eso, en el código adoptamos medidas adicionales contra el desbordamiento de enteros de la siguiente manera:


d[e.b] = max(-INF, d[e.a] + e.cost);

La implementación anterior busca un ciclo negativo alcanzable desde algún vértice de partida $v$ ; sin embargo, el algoritmo se puede modificar para buscar simplemente cualquier ciclo negativo en el grafo. Para esto hay que poner todas las distancias $d[i]$ en cero y no en infinito — como si buscáramos el camino más corto desde todos los vértices simultáneamente; la validez de la detección de un ciclo negativo no se ve afectada.

Para más sobre este tema — véase el artículo aparte, Encontrar un ciclo negativo en el grafo.

Algoritmo SPFA (Shortest Path Faster Algorithm)

SPFA es una mejora del algoritmo de Bellman-Ford que aprovecha el hecho de que no todos los intentos de relajación van a funcionar. La idea principal es crear una cola que contenga solo los vértices que fueron relajados pero que todavía podrían relajar a sus vecinos. Y cada vez que se pueda relajar a algún vecino, hay que ponerlo en la cola. Este algoritmo también se puede usar para detectar ciclos negativos, al igual que Bellman-Ford.

El peor caso de este algoritmo es igual al $O(n m)$ de Bellman-Ford, pero en la práctica funciona mucho más rápido y algunas personas afirman que incluso funciona en $O(m)$ en promedio. Sin embargo hay que tener cuidado, porque este algoritmo es determinista y es fácil crear contraejemplos que hacen que el algoritmo corra en $O(n m)$ .

Hay algunos cuidados que tomar en la implementación, como el hecho de que el algoritmo continúa para siempre si hay un ciclo negativo. Para evitar esto, es posible crear un contador que almacene cuántas veces se relajó un vértice y detener el algoritmo tan pronto como algún vértice se haya relajado por $n$ -ésima vez. Nótese, además, que no hay razón para poner un vértice en la cola si ya está en ella.


const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

bool spfa(int s, vector<int>& d) {
    int n = adj.size();
    d.assign(n, INF);
    vector<int> cnt(n, 0);
    vector<bool> inqueue(n, false);
    queue<int> q;

    d[s] = 0;
    q.push(s);
    inqueue[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inqueue[v] = false;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                if (!inqueue[to]) {
                    q.push(to);
                    inqueue[to] = true;
                    cnt[to]++;
                    if (cnt[to] > n)
                        return false;  // ciclo negativo
                }
            }
        }
    }
    return true;
}

Problemas relacionados en jueces en línea

Una lista de tareas que se pueden resolver usando el algoritmo de Bellman-Ford:

Véase también la lista de problemas en el artículo Encontrar el ciclo negativo en un grafo.