BFS 0-1

Es bien sabido que se pueden encontrar los caminos más cortos entre una sola fuente y todos los demás vértices en $O(|E|)$ usando Búsqueda en Anchura en un grafo no ponderado, es decir, la distancia es el número mínimo de aristas que hay que recorrer de la fuente a otro vértice. También podemos interpretar ese grafo como un grafo ponderado donde cada arista tiene peso $1$ . Si no todas las aristas del grafo tienen el mismo peso, entonces necesitamos un algoritmo más general, como Dijkstra, que corre en $O(|V|^2 + |E|)$ o $O(|E| \log |V|)$ .

Sin embargo, si los pesos están más restringidos, a menudo podemos hacer mejor. En este artículo mostramos cómo usar BFS para resolver el problema SSSP (single-source shortest path) en $O(|E|)$ , si el peso de cada arista es $0$ o $1$ .

Algoritmo

Podemos desarrollar el algoritmo estudiando de cerca el algoritmo de Dijkstra y pensando en las consecuencias que implica nuestro grafo especial. La forma general del algoritmo de Dijkstra es (acá se usa un set para la cola de prioridad):


d.assign(n, INF);
d[s] = 0;
set<pair<int, int>> q;
q.insert({0, s});
while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());
 
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
 
        if (d[v] + w < d[u]) {
            q.erase({d[u], u});
            d[u] = d[v] + w;
            q.insert({d[u], u});
        }
    }
}

Podemos notar que la diferencia entre las distancias de la fuente s a dos vértices en la cola difiere en a lo sumo uno. En particular, sabemos que $d[v] \le d[u] \le d[v] + 1$ para cada $u \in Q$ . La razón es que solo agregamos a la cola vértices con distancia igual o con distancia más uno durante cada iteración. Suponiendo que existe un $u$ en la cola con $d[u] - d[v] > 1$ , entonces $u$ debió haberse insertado en la cola vía un vértice distinto $t$ con $d[t] \ge d[u] - 1 > d[v]$ . Sin embargo esto es imposible, porque el algoritmo de Dijkstra itera sobre los vértices en orden creciente.

Esto significa que el orden de la cola se ve así:

$Q = \underbrace{v}$

Esta estructura es tan simple que no necesitamos una cola de prioridad de verdad: usar un árbol binario balanceado sería excesivo. Podemos usar simplemente una cola normal, y agregar vértices nuevos al principio si la arista correspondiente tiene peso $0$ , es decir, si $d[u] = d[v]$ , o al final si la arista tiene peso $1$ , es decir, si $d[u] = d[v] + 1$ . De esta forma la cola sigue ordenada en todo momento.


vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            if (w == 1)
                q.push_back(u);
            else
                q.push_front(u);
        }
    }
}

Algoritmo de Dial

Podemos extender esto todavía más si permitimos que los pesos de las aristas sean aún más grandes. Si cada arista del grafo tiene peso $\le k$ , entonces las distancias de los vértices en la cola diferirán en a lo sumo $k$ de la distancia de $v$ a la fuente. Así que podemos mantener $k + 1$ buckets para los vértices en la cola, y cada vez que el bucket correspondiente a la distancia más chica se vacía, hacemos un shift cíclico para obtener el bucket con la siguiente distancia más alta. Esta extensión se llama algoritmo de Dial.

BFS 0-1

Algoritmo

Algoritmo de Dial

Problemas de práctica