Herramientas de usuario
algoritmos-oia:grafos:dijkstra
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Próxima revisión | Revisión previa Próxima revisión Ambos lados, revisión siguiente | ||
|
algoritmos-oia:grafos:dijkstra [2017/11/23 01:56] sebach creado |
algoritmos-oia:grafos:dijkstra [2017/12/30 09:05] sebach [Más simple pero más lento ( O(V^2) )] |
||
|---|---|---|---|
| Línea 19: | Línea 19: | ||
| 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. | ||
| - | DEMO ? GRAFIQUITOS ? | + | FIXME [DEMO ? GRAFIQUITOS ?] |
| ==== Más simple pero más lento ( O(V^2) ) ==== | ==== Más simple pero más lento ( 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 dijkstraLento(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); | ||
| + | | ||
| + | queue<int> q; | ||
| + | q.push(s); | ||
| + | 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 poquito más compleja pero mucho más eficiente ( O(E*log(V)) ) ==== | ==== Implementación un poquito más compleja pero mucho más eficiente ( O(E*log(V)) ) ==== | ||
algoritmos-oia/grafos/dijkstra.txt · Última modificación: 2018/07/09 04:57 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
