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 | |||
|
algoritmos-oia:grafos:dijkstra [2018/01/02 12:11] sebach [Idea] |
algoritmos-oia:grafos:dijkstra [2018/07/09 04:57] (actual) santo |
||
|---|---|---|---|
| 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.1514895105.txt.gz · Última modificación: 2018/01/02 12:11 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
