Algoritmo de Dijkstra

Se da un grafo ponderado dirigido o no dirigido con $n$ vértices y $m$ aristas. Los pesos de todas las aristas son no negativos. También se da un vértice de partida $s$ . Este artículo trata de encontrar las longitudes de los caminos más cortos desde un vértice de partida $s$ hacia todos los demás vértices, y de devolver los propios caminos más cortos.

Este problema también se llama problema de caminos más cortos desde una sola fuente (single-source shortest paths).

Algoritmo

Aquí está un algoritmo descrito por el científico de la computación neerlandés Edsger W. Dijkstra en 1959.

Creamos un arreglo $d[]$ donde para cada vértice $v$ guardamos en $d[v]$ la longitud actual del camino más corto de $s$ a $v$ . Inicialmente $d[s] = 0$ , y para todos los demás vértices esta longitud es igual a infinito. En la implementación se elige como infinito un número suficientemente grande (del que se garantiza que es mayor que cualquier longitud de camino posible).

$d[v] = \infty,~ v \ne s$

Además, mantenemos un arreglo booleano $u[]$ que almacena, para cada vértice $v$ , si está marcado. Inicialmente todos los vértices están desmarcados:

$u[v] = {\rm false}$

El algoritmo de Dijkstra realiza $n$ iteraciones. En cada iteración se elige un vértice $v$ no marcado que tenga el menor valor $d[v]$ :

Evidentemente, en la primera iteración se selecciona el vértice de partida $s$ .

El vértice seleccionado $v$ se marca. A continuación, desde el vértice $v$ se realizan relajaciones (relaxations): se consideran todas las aristas de la forma $(v,\text{to})$ , y para cada vértice $\text{to}$ el algoritmo intenta mejorar el valor $d[\text{to}]$ . Si la longitud de la arista actual es $len$ , el código de la relajación es:

$d[\text{to}] = \min (d[\text{to}], d[v] + len)$

Después de considerar todas esas aristas, termina la iteración actual. Finalmente, tras $n$ iteraciones, todos los vértices estarán marcados y el algoritmo termina. Afirmamos que los valores encontrados $d[v]$ son las longitudes de los caminos más cortos desde $s$ hasta todos los vértices $v$ .

Nótese que si algunos vértices son inalcanzables desde el vértice de partida $s$ , los valores $d[v]$ para ellos permanecerán infinitos. Obviamente, las últimas iteraciones del algoritmo elegirán esos vértices, pero no se hará ningún trabajo útil con ellos. Por lo tanto, el algoritmo se puede detener en cuanto el vértice seleccionado tenga distancia infinita.

Restauración de los caminos más cortos

Por lo general no solo hacen falta las longitudes de los caminos más cortos, sino también los propios caminos más cortos. Veamos cómo mantener información suficiente para restaurar el camino más corto de $s$ a cualquier vértice. Mantendremos un arreglo de predecesores $p[]$ en el que, para cada vértice $v \ne s$ , $p[v]$ es el penúltimo vértice en el camino más corto de $s$ a $v$ . Aquí usamos el hecho de que si tomamos el camino más corto hasta algún vértice $v$ y quitamos $v$ de este camino, obtenemos un camino que termina en el vértice $p[v]$ , y este camino será el más corto para el vértice $p[v]$ . Este arreglo de predecesores se puede usar para restaurar el camino más corto hasta cualquier vértice: empezando por $v$ , tomamos repetidamente el predecesor del vértice actual hasta llegar al vértice de partida $s$ , y así obtenemos el camino más corto pedido con los vértices listados en orden inverso. Así, el camino más corto $P$ hasta el vértice $v$ es igual a:

$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$

Construir este arreglo de predecesores es muy simple: en cada relajación exitosa, es decir, cuando para algún vértice seleccionado $v$ hay una mejora en la distancia hasta algún vértice $\text{to}$ , actualizamos el vértice predecesor de $\text{to}$ con el vértice $v$ :

$p[\text{to}] = v$

Demostración

La afirmación principal sobre la que se basa la corrección del algoritmo de Dijkstra es la siguiente:

Después de que cualquier vértice $v$ queda marcado, la distancia actual hasta él $d[v]$ es la más corta, y ya no volverá a cambiar.

La demostración se hace por inducción. Para la primera iteración este enunciado es obvio: el único vértice marcado es $s$ , y la distancia hasta él $d[s] = 0$ es efectivamente la longitud del camino más corto hasta $s$ . Ahora supongamos que este enunciado es cierto para todas las iteraciones anteriores, es decir, para todos los vértices ya marcados; vamos a probar que no se viola después de que termina la iteración actual. Sea $v$ el vértice seleccionado en la iteración actual, es decir, $v$ es el vértice que el algoritmo va a marcar. Ahora hay que demostrar que $d[v]$ es efectivamente igual a la longitud del camino más corto hasta él $l[v]$ .

Consideremos el camino más corto $P$ hasta el vértice $v$ . Este camino se puede partir en dos partes: $P_1$ , que consiste solo en nodos marcados (al menos el vértice de partida $s$ forma parte de $P_1$ ), y el resto del camino $P_2$ (puede incluir un vértice marcado, pero siempre empieza con un vértice no marcado). Denotemos el primer vértice del camino $P_2$ como $p$ , y el último vértice del camino $P_1$ como $q$ .

Primero demostramos nuestro enunciado para el vértice $p$ , es decir, vamos a probar que $d[p] = l[p]$ . Esto es casi obvio: en una de las iteraciones anteriores elegimos el vértice $q$ y realizamos una relajación desde él. Como (en virtud de la elección del vértice $p$ ) el camino más corto hasta $p$ es el camino más corto hasta $q$ más la arista $(p,q)$ , la relajación desde $q$ fijó el valor de $d[p]$ a la longitud del camino más corto $l[p]$ .

Como los pesos de las aristas son no negativos, la longitud del camino más corto $l[p]$ (que acabamos de demostrar que es igual a $d[p]$ ) no supera la longitud $l[v]$ del camino más corto hasta el vértice $v$ . Dado que $l[v] \le d[v]$ (porque el algoritmo de Dijkstra no pudo haber encontrado un camino más corto que el más corto posible), obtenemos la desigualdad:

$d[p] = l[p] \le l[v] \le d[v]$

Por otro lado, como ambos vértices $p$ y $v$ están desmarcados, y la iteración actual eligió el vértice $v$ y no $p$ , obtenemos otra desigualdad:

$d[p] \ge d[v]$

De estas dos desigualdades concluimos que $d[p] = d[v]$ , y entonces a partir de las igualdades encontradas antes obtenemos:

$d[v] = l[v]$

Q.E.D.

Implementación

El algoritmo de Dijkstra realiza $n$ iteraciones. En cada iteración selecciona un vértice no marcado $v$ con el menor valor $d[v]$ , lo marca y revisa todas las aristas $(v, \text{to})$ intentando mejorar el valor $d[\text{to}]$ .

El tiempo de ejecución del algoritmo consiste en:

$n$ búsquedas de un vértice con el menor valor $d[v]$ entre $O(n)$ vértices no marcados
$m$ intentos de relajación

Para la implementación más simple de estas operaciones, en cada iteración la búsqueda del vértice requiere $O(n)$ operaciones, y cada relajación se puede realizar en $O(1)$ . Por lo tanto, el comportamiento asintótico resultante del algoritmo es:

$O(n^2+m)$

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$ , el problema se puede resolver con complejidad $O(n \log n + m)$ . El algoritmo y la implementación se pueden encontrar en el artículo Dijkstra en grafos dispersos.


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);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }
        
        if (d[v] == INF)
            break;
        
        u[v] = true;
        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;
            }
        }
    }
}

Aquí el grafo $\text{adj}$ se almacena como lista de adyacencia: para cada vértice $v$ , $\text{adj}[v]$ contiene la lista de aristas que salen de este vértice, es decir, la lista de pair<int,int> donde el primer elemento del par es el vértice en el otro extremo de la arista, y el segundo elemento es el peso de la arista.

La función toma el vértice de partida $s$ y dos vectores que se usarán como valores de retorno.

En primer lugar, el código inicializa los arreglos: distancias $d[]$ , marcas $u[]$ y predecesores $p[]$ . Luego realiza $n$ iteraciones. En cada iteración se selecciona el vértice $v$ que tiene la menor distancia $d[v]$ entre todos los vértices no marcados. Si la distancia al vértice seleccionado $v$ es igual a infinito, el algoritmo se detiene. En caso contrario el vértice se marca, y se revisan todas las aristas que salen de este vértice. Si es posible relajar a lo largo de la arista (es decir, se puede mejorar la distancia $d[\text{to}]$ ), se actualizan la distancia $d[\text{to}]$ y el predecesor $p[\text{to}]$ .

Después de realizar todas las iteraciones, el arreglo $d[]$ almacena las longitudes de los caminos más cortos hasta todos los vértices, y el arreglo $p[]$ almacena los predecesores de todos los vértices (excepto el vértice de partida $s$ ). El camino hasta cualquier vértice $t$ se puede restaurar de la siguiente manera:


vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

Referencias

Edsger Dijkstra. A note on two problems in connexion with graphs [1959]
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]