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 12:01] 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 |}} | ||
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$. |