Dijkstra en grafos dispersos

El enunciado del problema, el algoritmo con implementación y la demostración se pueden encontrar en el artículo algoritmo de Dijkstra.

Algoritmo

Recordamos que en la derivación de la complejidad del algoritmo de Dijkstra usamos dos factores: el tiempo de encontrar el vértice no marcado con la menor distancia $d[v]$ , y el tiempo de la relajación, es decir, el tiempo de cambiar los valores $d[\text{to}]$ .

En la implementación más simple estas operaciones requieren $O(n)$ y $O(1)$ de tiempo. Por lo tanto, como hacemos la primera operación $O(n)$ veces y la segunda $O(m)$ veces, obtuvimos la complejidad $O(n^2 + m)$ .

Está claro que esta complejidad es óptima para un grafo denso, es decir, cuando $m \approx n^2$ . Sin embargo en grafos dispersos, cuando $m$ es mucho menor que el número máximo de aristas $n^2$ , la complejidad se vuelve menos óptima por el primer término. Así que es necesario mejorar el tiempo de ejecución de la primera operación (y por supuesto sin afectar demasiado la segunda).

Para lograrlo podemos usar una variación de varias estructuras de datos auxiliares. La más eficiente es el Fibonacci heap, que permite que la primera operación corra en $O(\log n)$ y la segunda en $O(1)$ . Por lo tanto obtenemos la complejidad $O(n \log n + m)$ para el algoritmo de Dijkstra, que también es el mínimo teórico para el problema de búsqueda de caminos más cortos. Por lo tanto este algoritmo trabaja de forma óptima, y los Fibonacci heaps son la estructura de datos óptima. No existe ninguna estructura de datos que pueda hacer ambas operaciones en $O(1)$ , porque eso también permitiría ordenar una lista de números aleatorios en tiempo lineal, lo cual es imposible. Curiosamente existe un algoritmo de Thorup que encuentra el camino más corto en $O(m)$ , pero solo funciona para pesos enteros y usa una idea completamente distinta. Así que esto no lleva a contradicciones. Los Fibonacci heaps dan la complejidad óptima para esta tarea. Sin embargo son bastante complejos de implementar, y también tienen una constante oculta bastante grande.

Como compromiso se pueden usar estructuras de datos que hacen ambos tipos de operaciones (extraer un mínimo y actualizar un ítem) en $O(\log n)$ . Entonces la complejidad del algoritmo de Dijkstra es $O(n \log n + m \log n) = O(m \log n)$ .

C++ provee dos de esas estructuras: set y priority_queue. La primera se basa en árboles rojo-negro, y la segunda en heaps. Por lo tanto priority_queue tiene una constante oculta más chica, pero también tiene un inconveniente: no soporta la operación de borrar un elemento. Por eso hay que hacer un “workaround”, que de hecho lleva a un factor ligeramente peor $\log m$ en lugar de $\log n$ (aunque en términos de complejidad son idénticos).

Implementación

set

Empecemos con el contenedor set. Como necesitamos guardar vértices ordenados por sus valores $d[]$ , es conveniente guardar pares reales: la distancia y el índice del vértice. Como resultado, en un set los pares se ordenan automáticamente por sus distancias.


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

Ya no necesitamos el arreglo $u[]$ de la implementación normal del algoritmo de Dijkstra. Usaremos el set para guardar esa información, y también para encontrar el vértice con la distancia más corta. Actúa un poco como una cola. El bucle principal se ejecuta hasta que no hay más vértices en el set/cola. Se extrae un vértice con la menor distancia, y para cada relajación exitosa primero borramos el par viejo, y después de la relajación agregamos el par nuevo a la cola.

priority_queue

La diferencia principal con la implementación con set es que en muchos lenguajes, incluido C++, no podemos borrar elementos de la priority_queue (aunque los heaps pueden soportar esa operación en teoría). Por lo tanto hay que usar un workaround: simplemente no borramos el par viejo de la cola. Como resultado un vértice puede aparecer varias veces con distinta distancia en la cola al mismo tiempo. Entre esos pares solo nos interesan los pares donde el primer elemento es igual al valor correspondiente en $d[]$ ; todos los demás pares son viejos. Por lo tanto hay que hacer una pequeña modificación: al principio de cada iteración, después de extraer el siguiente par, chequeamos si es un par importante o si ya es un par viejo y procesado. Este chequeo es importante; si no, la complejidad puede subir hasta $O(n m)$ .

Por defecto una priority_queue ordena elementos en orden descendente. Para que ordene en orden ascendente, podemos o guardar las distancias negadas, o pasarle una función de ordenamiento distinta. Vamos a hacer la segunda opción.


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

En la práctica la versión con priority_queue es un poco más rápida que la versión con set.

Curiosamente, un technical report de 2007 concluyó que la variante del algoritmo que no usa operaciones decrease-key corría más rápido que la variante con decrease-key, con una brecha de rendimiento mayor para grafos dispersos.

Deshacerse de los pares

Se puede mejorar un poco más el rendimiento si no se guardan pares en los contenedores, sino solo los índices de los vértices. En este caso hay que sobrecargar el operador de comparación: debe comparar dos vértices usando las distancias guardadas en $d[]$ .

Como resultado de la relajación, la distancia de algunos vértices va a cambiar. Sin embargo la estructura de datos no se reordenará sola. De hecho, cambiar distancias de vértices en la cola podría destruir la estructura de datos. Como antes, hay que sacar el vértice antes de relajarlo, y después insertarlo de nuevo.

Como solo podemos borrar de set, esta optimización solo aplica al método set, y no funciona con la implementación priority_queue. En la práctica esto aumenta significativamente el rendimiento, especialmente cuando se usan tipos de datos más grandes para guardar distancias, como long long o double.