Dijkstra em grafos esparsos

Algoritmo

Recordamos que na complexidade do algoritmo de Dijkstra usamos dois fatores:: o tempo da procura vértices não marcados com a menor distância $d[v]$, e o tempo do aprimoramento desse valor, i.e. o tempo de mudar o valor $d[\text{to}]$.

Na implementação essas operações requerem $O(n)$ e $O(1)$. Portanto, executamos a primeira operação $O(n)$ vezes, e a segunda $O(m)$ vezes, obtendo a complexidade $O(n^2 + m)$.

Fica claro que essa complexidade é otimizada para um grafo denso, i.e. quando $m \approx n^2$. Entretanto em grafos esparsos, quando $m$ é bem menor que o número máximo de arestas $n^2$, a complexidade fica menos otimizada. Assim, é necessário aprimorar o tempo de execução da primeira operação.

Para conseguir isso, podemos usar uma variação de várias estruturas de dados auxiliares. A mais eficiente é a "Fibonacci heap", permitindo que a primeira operação seja executada em $O(\log n)$, e a segunda operação em $O(1)$. Obtendo a complexidade $O(n \log n + m)$ para o algoritmo de Dijkstra, na qual, teoricamente, é a mínima para o problema dos caminhos mais curtos. Portanto, o algoritmo é otimizado. Não existe nenhuma estrutura de dados, que possa executar as duas operações em tempo $O(1)$, porque isso também permitiria ordenar uma lista de números aleatórios em tempo linear, o que é impossível. Curiosamente, existe um algoritmo por Thorup que encontra o caminho mais curto em tempo $O(m)$, entretanto ele funciona apenas com pesos inteiros, e usa uma ideia completamente diferente. Fibonacci heaps fornece a complexidade otimizada para essa tarefa. No entanto, eles são bastante complexos de implementar e também possuem uma constante oculta bastante grande.

Você pode usar estruturas de dados para performar ambas operações (extrair or mínimo e atualizar um item) em $O(\log n)$. A complexidade do algoritmo de Dijkstra fica $O(n \log n + m \log n) = O(m \log n)$.

C++ fornece duas estruturas de dados que podem ajudar: set e priority_queue. A primeira é baseada em árvores rubro-negras, e a segunda em heaps. Assim, priority_queue tem uma constante escondida menor, mas também tem uma desvantagem: não suporta a operação de remover um determinado elemento x, como "delete(x)". Por causa disso, precisamos fazer um "trabalho extra", que leva a um pior fator: $\log m$ em vez de $\log n$ (embora em termos de complexidade eles são idênticos).

Implementação

set

Vamos começar com o recipiente set. Precisamos armazenar nele vértices ordenados por seus valores de distância, $d[$ $]$, convém armazenamos em pares: a distância e o índice do vértice. Em um set pares são automaticamente ordenados por suas distâncias.

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

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);

    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 to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                q.erase({d[to], to});
                d[to] = d[v] + len;
                p[to] = v;
                q.insert({d[to], to});
            }
        }
    }
}

Não precisamos mais da array $u[$ $]$ da implementação do Dijkstra "normal". Usamos set para armazenar a informação, e também achar o vértice com a menor distância. Os loops são executados até que não haja mais vértices no set/queue. Um vértice com a menor distância é extraído, e para cada aprimoramento de distância nós removemos o par antigo, depois do aprimoramento, armazenamos o novo par na queue.

priority_queue

A principal diferença para a implementação com set é que não removemos elementos da priority_queue (embora "heaps" suportam essa operação na teoria). Portanto, precisamos trapacear um pouco. Nós não deletaremos o par antigo da queue/set. Como resultado, um vértice pode aparecer múltiplas vezes com distâncias diferentes na queue. Dentre esses pares apenas estamos interessados em pares onde o primeiro elemento é igual ao valor correspondente em $d[$ $]$, todos os outros pares são "antigos". Portanto, precisamos fazer uma modificação: no começo de cada iteração, depois de extrair o próximo par, checamos se é um par "importante" ou se é apenas um par "antigo". Essa checagem é importante, caso contrário a complexidade pode ser incrementada para $O(n m)$.

Por padrão priority_queue ordena elementos em ordem descendente($maior$ ... $menor$). Para poder ordenar em ordem ascendente, podemos executá-la em uma função diferente.

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

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);

    d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;   //greater: ordem ascendente na priority queue
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

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

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

Em prática a versão da priority_queue é um pouco mais rápida que a versão com set.

Se livrando de pares

Você pode aprimorar a performance um pouco mais se você não armazenar pares nos recipientes, mas apenas os índices dos vértices. Nesse caso precisamos fazer um overload do operador de comparação: precisa comparar dois vértices usando as distâncias armazenadas em $d[$ $]$.

Como resultado do aprimoramento, a distância de alguns vértices irão mudar. Entretanto, a estrutura de dados não irá reordenar-se automaticamente. Mudar as distâncias dos vértices na queue, pode destruir a estrutura de dados. Como antes, precisamos remover o vértice antes do aprimoramento, e depois disso colocá-lo novamente.

Desde que apenas podemos remover de set, essa otimização é aplicável apenas no método com set, e não funciona com a implementação da priority_queue. Em prática, isso aumenta o desempenho em casos onde os dados são muito grandes para armazenar as distâncias, como long long ou double.