Herramientas de usuario
algoritmos-oia:grafos:dijkstra
Diferencias
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 [2018/01/02 11:59] sebach [Idea] |
algoritmos-oia:grafos:dijkstra [2018/07/09 04:57] (actual) santo |
||
|---|---|---|---|
| Línea 20: | Línea 20: | ||
| - | 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$ | + | 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 |}} | {{ :algoritmos-oia:grafos:dijkstra1.png?400 |}} | ||
| - | Sacamos al nodo $0$ de la priority_queue, que es el nodo más cercano, y vemos qué pasa con los vecinos | + | 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 |}} | {{ :algoritmos-oia:grafos:dijkstra2.png?400 |}} | ||
| - | Ir al nodo $2$ con distancia $0+7$ es mejor que la que teníamos, infinito, entonces actualizamos. | + | 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 |}} | {{ :algoritmos-oia:grafos:dijkstra3.png?400 |}} | ||
| Línea 100: | Línea 100: | ||
| - | ==== Más simple pero más lento ( O(V^2) ) ==== | + | ==== Implementación simple ( $O(V^2)$ ) ==== |
| Línea 107: | 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 114: | 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 146: | 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 193: | 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$. | ||
algoritmos-oia/grafos/dijkstra.1514894366.txt.gz · Última modificación: 2018/01/02 11:59 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
