OIA-Wiki

Dado un grafo con aristas con longitudes positivas, y un nodo de “comienzo” (al cual llamaremos source por la definición en inglés, o S para resumir), encontrar el camino más corto desde éste nodo hasta todos los demás.

Comentario: la idea de nombrar a algunas cosas según su significado en inglés es que en internet hay muuuucha más documentación y textos para leer sobre esto (y en general, de cualquier cosa) en inglés. Entonces está bueno ir acostumbrándose a algunas definiciones en inglés por si quieren googlear algo.

La idea es arrancar yendo desde el nodo source al nodo más cercano. Supongamos que el nodo más cercano es el nodo A y está a distancia 4. Puede haber un camino más corto para, desde el source, llegar hasta A?

No, porque si lo hubiera, por ejemplo si el camino fuera $S$->$B$->$A$, significa que hay otro nodo (el $B$) que está a menos distancia de $A$, pero por definición sabemos que eso no pasa.

También vamos a guardar la información de “hasta este momento, la distancia más corta desde el source hasta el nodo $X$ es $D$”. Entonces si hay una arista desde $S$ hasta $B$ de longitud $7$, guardamos ese número.

Una vez que guardamos esa información para todos los vecinos de $S$, agarramos al nodo más cercano hasta $S$ de los que todavía no vimos, en nuestro caso $A$.

Miramos los vecinos que no visitamos (o sea, a $S$ no lo vamos a mirar), y nos fijamos si la distancia desde $S$ hasta el nodo actual sumado a la longitud de la arista $AV$ siendo $V$ un vecino, es menor que la distancia que teníamos hasta el momento desde $S$ hasta $V$. Si es más chico, actualizamos el valor como esa suma.

Tenemos este grafo, y queremos ir del nodo $S=a$ (nodo $0$, que empieza con distancia $0$ y el resto con infinito) hasta el nodo $b=5$ (imágenes tomadas de esta clase de Melanie Sclar)

Sacamos al nodo $1$ de la priority_queue, que es el nodo más cercano, y vemos qué pasa con los vecinos

Ir al nodo $2$ con distancia $0+7$ es mejor (más corto) que con la distancia que teníamos, infinito, entonces actualizamos.

Lo mismo con los nodos $3$ y $4$, vamos a actualizar con la distancia $0$ más la longitud de la arista.

Terminamos de ver los vecinos del nodo $1$, lo marcamos como visitado.

Agarramos al nodo más cercano de los no visitados que tenemos, el $2$, y miramos sus vecinos no visitados, a los que todavía podríamos encontrar un camino mejor

El camino que tenemos hasta el nodo $3$ (vecino del $2$), es peor que yendo desde el $2$ con el camino que tenemos hasta el $2$?

No, entonces, no actualizamos la distancia

La distancia que tenemos hasta el nodo $4$, es peor que yendo desde el nodo $2$?

Sí, entonces actualizamos

Ya vimos todos los vecinos del $2$ sin visitar, lo marcamos como visitado y nos olvidamos de este nodo

Agarramos al nodo $3$, el más cercano de los no visitados hasta acá

La distancia que tenemos hasta el nodo $4$, es peor que ir desde el $3$ con la distancia desde el source hasta él, $9$? Sí, entonces actualizamos

La distancia que tenemos hasta el nodo $6$, $14$, es peor que ir desde el nodo $3$ hasta el $4$?

Sí, entonces actualizamos la distancia al nodo $6$

Ya vimos todos los vecinos del nodo $3$, entonces lo marcamos como visitado

Agarramos al nodo más cercano que tenemos, el $6$, y miramos sus vecinos no visitados

La distancia al nodo $5$ que tenemos guardada es peor que yendo desde el $6$? Sí, entonces actualizamos.

Ya miramos todos los vecinos del $6$ sin visitar, lo marcamos como visitado.

Luego, podemos agarrar a cualquiera de los nodos $4$ ó $5$ (la distancia que tenemos es igual, $20$), intentar ir al otro, ver que la distancia es mayor, no actualizar, y terminar el algoritmo.

dijkstra-lento.cpp

// Tenemos la matriz de vecinos vector< vector<int> > matriz que en matriz[x][y] guarda cuanto mide esa arista, -1 si no existe
 
int dijkstraCuadratico(int s, int dest){
    int n = matriz.size();
    const int INF = 100000000;
    vector<int> dist(n, INF);
    vector<int> prev(n, -1);
    vector<bool> vis(n, false);
 
    dist[s]=0;
    forn(paso, n){
        int nodoMasCercano=-1;
        forn(i, n){
            if(!vis[i]){
                if(nodoMasCercano==-1 || dist[nodoMasCercano]>dist[i]){
                    nodoMasCercano=i;
                }
            }
        }
        vis[nodoMasCercano]=true;
        forn(i, n){
            int val = dist[nodoMasCercano]+matriz[nodoMasCercano][i];
            if(val<dist[i]){
                dist[i]=val;
                prev[i]=nodoMasCercano;
            }
        }
    }
    // Imprimimos el camino, inverso. Para imprimirlo bien vamos guardando en un vector y lo imprimimos al revés
    int estoy = dest;
    cout<<estoy<<endl;
    while(estoy!=s){
        estoy=prev[estoy];
        cout<<estoy<<endl;
    }
    return dist[dest];
}

Ahora, en vez de tener la matriz de dimensiones $n$ x $n$, vamos tener un grafo que guarde las aristas de cada nodo con sus longitudes. Si no habría que recorrer todos los nodos desde cada uno para ver los vecinos y la complejidad se nos iría al caso anterior.

dijkstra.cpp

// Tenemos un vector<vector<pair<int,int> > > grafo donde los elementos del vector i son del estilo (distancia, vecino)
 
int dijkstra(int s, int dest){
    int n = grafo.size();
    const int INF = 100000000;
    vector<int> dist(n, INF);
    vector<int> prev(n, -1);
    vector<bool> vis(n, false);
 
    priority_queue< pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > q;
    q.push(make_pair(0, s));
    dist[s]=0;
    while(!q.empty()){
        int nodoMasCercano=q.top().second;
        q.pop();
        if(!vis[nodoMasCercano]){
			vis[nodoMasCercano]=true;
			forn(i, grafo[nodoMasCercano].size()){
				int vecino = grafo[nodoMasCercano][i].second;
				int longitud = grafo[nodoMasCercano][i].first; // si guardaramos (vecino, distancia) esto sería al revés first y second
				int val = dist[nodoMasCercano]+longitud;
				if(val<dist[vecino]){
					dist[vecino]=val;
					prev[vecino]=nodoMasCercano;
					q.push(make_pair(val, vecino));
				}
			}
		}
    }
    // Imprimimos el camino, inverso. Para imprimirlo bien vamos guardando en un vector y lo imprimimos al revés
    int estoy = dest;
    cout<<estoy<<endl;
    while(estoy!=s){
        estoy=prev[estoy];
        cout<<estoy<<endl;
    }
    return dist[dest];
}

Observemos que, si hay $o(\frac{V^2}{\lg V})$ aristas en el grafo, la complejidad resultante será mejor que el caso anterior. De no ser así, la complejidad de esta versión más complicada es peor que la versión anterior, y por eso en general no conviene utilizarla si el grafo tiene muchísimas aristas: Si para cierta constante $k$ tenemos $E = k N^2$, la complejidad de esta versión es $k N^2 \lg N$, que si el $k$ es apreciable es claramente peor que la anterior por un factor $\lg N$.