Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:dijkstra [2017/11/23 01:56]
sebach creado
+++ 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)) )]
@@ 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.
-DEMO ? GRAFIQUITOS ?
+FIXME [DEMO ? GRAFIQUITOS ?]
 ==== 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)) ) ====
+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.
+<code cpp dijkstra.cpp>
+// Tenemos un vector<vector<pair<int,int> > > grafo donde los elementos del vector i son del estilo (distancia, vecino)
+int dijkstra(int s, int dest){
+    int n = grafo.size();
+    const int INF = 100000000;
+    vector<int> dist(n, INF);
+    vector<int> prev(n, -1);
+    vector<bool> vis(n, false);
+    priority_queue< pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > q;
+    q.push(make_pair(0, s));
+    dist[s]=0;
+    while(!q.empty()){
+        int nodoMasCercano=q.top().second;
+        q.pop();
+        if(!vis[nodoMasCercano]){
+ vis[nodoMasCercano]=true;
+ forn(i, grafo[nodoMasCercano].size()){
+ int vecino = grafo[nodoMasCercano][i].second;
+ int longitud = grafo[nodoMasCercano][i].first; // si guardaramos (vecino, distancia) esto sería al revés first y second
+ int val = dist[nodoMasCercano]+longitud;
+ if(val<dist[vecino]){
+ dist[vecino]=val;
+ prev[vecino]=nodoMasCercano;
+ q.push(make_pair(val, vecino));
+ }
+ }
+ }
+    }
+    // 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>

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página