===== Dijkstra =====

==== Enunciado ====

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.

==== Idea ====

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 [[https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf|esta clase]] de Melanie Sclar)

{{ :algoritmos-oia:grafos:dijkstra1.png?400 |}}


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

{{ :algoritmos-oia:grafos:dijkstra2.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra3.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra7.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra8.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra9.png?400 |}}

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$?

{{ :algoritmos-oia:grafos:dijkstra10.png?400 |}}

No, entonces, no actualizamos la distancia

{{ :algoritmos-oia:grafos:dijkstra11.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra12.png?400 |}}

Sí, entonces actualizamos

{{ :algoritmos-oia:grafos:dijkstra13.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra14.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra15.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra16.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra18.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra19.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra20.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra22.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra23.png?400 |}}

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

{{ :algoritmos-oia:grafos:dijkstra24.png?400 |}}

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.


==== Implementación simple ( $O(V^2)$ ) ====


<code cpp 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];
}

</code>
==== Implementación un poco más compleja ( $O(E \lg V)$ ) ====

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.

<code cpp 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];
}


</code>

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$.