Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
algoritmos-oia:grafos:dijkstra [2017/12/30 09:37] sebach [Implementación un poquito más compleja pero mucho más eficiente ( O(E*log(V)) )] |
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? | 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 |}} | ||
+ | |||
+ | |||
+ | 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)$ ) ==== | ||
Línea 28: | Línea 107: | ||
// Tenemos la matriz de vecinos vector< vector<int> > matriz que en matriz[x][y] guarda cuanto mide esa arista, -1 si no existe | // Tenemos la matriz de vecinos vector< vector<int> > matriz que en matriz[x][y] guarda cuanto mide esa arista, -1 si no existe | ||
- | int dijkstraLento(int s, int dest){ | + | int dijkstraCuadratico(int s, int dest){ |
int n = matriz.size(); | int n = matriz.size(); | ||
const int INF = 100000000; | const int INF = 100000000; | ||
Línea 35: | Línea 114: | ||
vector<bool> vis(n, false); | vector<bool> vis(n, false); | ||
| | ||
- | queue<int> q; | ||
- | q.push(s); | ||
dist[s]=0; | dist[s]=0; | ||
forn(paso, n){ | forn(paso, n){ | ||
Línea 67: | Línea 144: | ||
</code> | </code> | ||
- | ==== Implementación un poquito más compleja pero mucho más eficiente ( O(E*log(V)) ) ==== | + | ==== 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. | 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. | ||
Línea 114: | Línea 191: | ||
</code> | </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$. |