0-1 BFS

É bem conhecido que você pode encontrar os caminhos mais curtos entre uma única fonte e todos os outros vértices em $O(|E|)$ usando uma BFS em um grafo sem pesos, ou seja, a distância é o número mínimo de arestas que você precisa para percorrer da fonte para outro vértice. Podemos interpretar esse grafo também como um grafo com pesos, em que cada aresta tem peso $1$. Se nem todas as arestas do grafo tiverem o mesmo peso, precisamos de um algoritmo mais geral, como o de Dijkstra executado em tempo $O(|V|^2 + |E|)$ ou $O(|E| \log |V|)$.

No entanto, se os pesos forem mais restritos, geralmente podemos fazer melhor. Neste artigo, demonstramos como podemos usar uma BFS para resolver o problema do caminho mais curto de origem única em $O(|E|)$, se os pesos de cada aresta forem $0$ ou $1$.

Algoritmo

Podemos desenvolver o algoritmo estudando de perto o algoritmo de Dijkstra e pensando nas consequências que o nosso grafo especial implica. A forma geral do algoritmo de Dijkstra é (aqui o set é usado para a priority queue):

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 a diferença entre as distâncias da fonte s e entre dois outros vértices da queue difere no máximo por 1. Especialmente, sabemos que $d[v] \le d[u] \le d[v] + 1$ para cada $u \in Q$. A razão para isso é que apenas adicionamos vértices com distância igual ou com distância "+1" para a queue em cada iteração. Supondo que exista um $u$ na queue com $d[u] - d[v] > 1$, então $u$ deve ter sido inserido na queue por um vértice diferente $t$ com $d[t] \ge d[u] - 1 > d[v]$. No entanto, isso é impossível, pois o algoritmo de Dijkstra itera sobre os vértices em ordem crescente.

Isso significa que a ordem da queue parece assim: $$Q = \underbrace{v}_{d[v]}, \dots, \underbrace{u}_{d[v]}, \underbrace{m}_{d[v]+1} \dots \underbrace{n}_{d[v]+1}$$

Essa estrutura é tão simples que não precisamos de uma priority queue, ou seja, uma árvore binária balanceada, é um exagero. Podemos simplesmente usar uma queue normal e anexar novos vértices no começo se a aresta correspondente tiver peso $0$, ou seja, se $d[u] = d[v]$, ou no final se a aresta tiver peso $1$, ou seja: $d[u] = d[v] + 1$. Dessa forma a queue permanece ordenada todo o tempo.

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);
        }
    }
}

Dial's algorithm

Podemos estender isso ainda mais se permitirmos que os pesos das arestas sejam ainda maiores. Se todas as arestas do grafo tiverem um peso $\le k$, as distâncias dos vértices na queue diferirão em no máximo $k$ da distância de $v$ à origem. Assim, podemos manter $k + 1$ buckets para os vértices na queue, e, sempre que o bucket correspondente à menor distância ficar vazio, fazemos uma mudança cíclica para obter o bucket com a próxima distância mais alta. Essa extensão do algoritmo é chamada Dial's algorithm.

Problemas