Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:dijkstra [2017/12/26 19:12]
sebach ↷ Page moved from algoritmos-oia:dijkstra to algoritmos-oia:grafos:dijkstra
+++ algoritmos-oia:grafos:dijkstra [2018/07/09 04:57] (actual)
santo
@@ Línea 11: / Línea 11: @@
 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.
+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.
+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.
+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.
+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.
-FIXME [DEMO ? GRAFIQUITOS ?]
-==== Más simple pero más lento ( O(V^2) ) ====
+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 |}}
-==== Implementación un poquito más compleja pero mucho más eficiente ( O(E*log(V)) ) ====
+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$.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página