jueves, octubre 21, 2010

Ruta más corta - Solución por el algoritmo de Dijkstra

Para solucionar el problema de la ruta más corta entre dos nodos de un grafo se puede utilizar el Algoritmo de Dijkstra, el cual sigue el siguiente procedimiento para calcular la ruta más corta desde el nodo origen hasta cada uno de los nodos del grafo:


  • Crea una listas de nodos para almacenar los nodos con distancia mínima ya calculada
  • Crear una cola de prioridad para los nodos pendientes de evaluar
  • Inserta el nodo origen a la cola de prioridad
  • Mientras que haya nodos en la cola de prioridad
    • Extrae el primer nodo de la cola de prioridad (tmp)
    • Agrega el nodo tmp a la lista de nodos ya calculados
    • Genera una lista de los nodos conectados al nodo tmp que no estén en la lista de ya calculados
    • Para cada nodo de la lista (nod)
      • Calcula la distancia al origen con la distancia entre tmp y nod más la distancia calculada entre el origen y tmp.
      • Si el nodo nod no está en la cola de prioridad lo agrega
      • Si el nodo nod ya está en la cola de prioridad y la distancia con la que está guardado en la cola es menor, lo deja como está y sino, lo actualiza con la distancia calculada
    • Fin
  • Fin
Al finalizar este procedimiento se tiene una lista con la menor distancia desde el origen a cada nodo.

La clase Grafo descrita en un post anterior se puede modificar para incluir un nuevo método que calcula la menor ruta usando el algoritmo de Dijkstra con dos nuevos métodos: uno para calcular la distancia entre el origen y todos lo nodos, guardando estos resultados en una lista, y el segundo para mostrar la ruta entre el origen y el nodo destino tomando la información de la lista de distancias calculadas.  Se implementa también un método adicional para verificar si un nodo ya está en la lista de terminados:

import java.util.*;

public class Grafo {
    char[]  nodos;  // Letras de identificación de nodo
    int[][] grafo;  // Matriz de distancias entre nodos
    String  rutaMasCorta;                           // distancia más corta
    int     longitudMasCorta = Integer.MAX_VALUE;   // ruta más corta
    List<Nodo>  listos=null;                        // nodos revisados Dijkstra

    // construye el grafo con la serie de identificadores de nodo en una cadena
    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }
    
    // encuentra la ruta más corta desde un nodo origen a un nodo destino
    public String encontrarRutaMinimaDijkstra(char inicio, char fin) {
        // calcula la ruta más corta del inicio a los demás
        encontrarRutaMinimaDijkstra(inicio);
        // recupera el nodo final de la lista de terminados
        Nodo tmp = new Nodo(fin);
        if(!listos.contains(tmp)) {
            System.out.println("Error, nodo no alcanzable");
            return "Bye";
        }
        tmp = listos.get(listos.indexOf(tmp));
        int distancia = tmp.distancia;  
        // crea una pila para almacenar la ruta desde el nodo final al origen
        Stack<Nodo> pila = new Stack<Nodo>();
        while(tmp != null) {
            pila.add(tmp);
            tmp = tmp.procedencia;
        }
        String ruta = "";
        // recorre la pila para armar la ruta en el orden correcto
        while(!pila.isEmpty()) ruta+=(pila.pop().id + " ");
        return distancia + ": " + ruta;
    }

    // encuentra la ruta más corta desde el nodo inicial a todos los demás
    public void encontrarRutaMinimaDijkstra(char inicio) {
        Queue<Nodo>   cola = new PriorityQueue<Nodo>(); // cola de prioridad
        Nodo            ni = new Nodo(inicio);          // nodo inicial
        
        listos = new LinkedList<Nodo>();// lista de nodos ya revisados
        cola.add(ni);                   // Agregar nodo inicial a la cola de prioridad
        while(!cola.isEmpty()) {        // mientras que la cola no esta vacia
            Nodo tmp = cola.poll();     // saca el primer elemento
            listos.add(tmp);            // lo manda a la lista de terminados
            int p = posicionNodo(tmp.id);   
            for(int j=0; j<grafo[p].length; j++) {  // revisa los nodos hijos del nodo tmp
                if(grafo[p][j]==0) continue;        // si no hay conexión no lo evalua
                if(estaTerminado(j)) continue;      // si ya fue agregado a la lista de terminados
                Nodo nod = new Nodo(nodos[j],tmp.distancia+grafo[p][j],tmp);
                // si no está en la cola de prioridad, lo agrega
                if(!cola.contains(nod)) {
                    cola.add(nod);
                    continue;
                }
                // si ya está en la cola de prioridad actualiza la distancia menor
                for(Nodo x: cola) {
                    // si la distancia en la cola es mayor que la distancia calculada
                    if(x.id==nod.id && x.distancia > nod.distancia) {
                        cola.remove(x); // remueve el nodo de la cola
                        cola.add(nod);  // agrega el nodo con la nueva distancia
                        break;          // no sigue revisando
                    }
                }
            }
        }
    }

    // verifica si un nodo ya está en lista de terminados
    public boolean estaTerminado(int j) {
        Nodo tmp = new Nodo(nodos[j]);
        return listos.contains(tmp);
    }

    // encontrar la ruta mínima por fuerza bruta
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 3);
        g.agregarRuta('a','e', 6);
        g.agregarRuta('a','f',10);
        g.agregarRuta('b','c', 5);
        g.agregarRuta('b','e', 2);
        g.agregarRuta('c','d', 8);
        g.agregarRuta('c','e', 9);
        g.agregarRuta('c','f', 7);
        g.agregarRuta('d','f', 4);
        g.agregarRuta('e','f', 4);
        char inicio = 'a';
        char fin    = 'd';
        String respuesta = g.encontrarRutaMinimaDijkstra(inicio, fin);
        System.out.println(respuesta);
    }
}


Esta clase requiere del uso adicionalmente de la clase Nodo, que va a servir para la cola de prioridad y para llevar registro de la distancia mínima desde el origen a un nodo, así como la referencia al nodo inmediatamente anterior:


public class Nodo implements Comparable<Nodo> {
    char id;
    int  distancia   = Integer.MAX_VALUE;
    Nodo procedencia = null;
    Nodo(char x, int d, Nodo p) { id=x; distancia=d; procedencia=p; }
    Nodo(char x) { this(x, 0, null); }
    public int compareTo(Nodo tmp) { return this.distancia-tmp.distancia; }
    public boolean equals(Object o) {
        Nodo tmp = (Nodo) o;
        if(tmp.id==this.id) return true;
        return false;
    }
}

33 comentarios:

  1. tengo una pregunta para que sirve la linea de codigo int longitudMasCorta = Integer.MAX_VALUE; mas espesificamente pera que se le pone ese Integer.Max_Value de ante mano muchas gracias por el aporte esta muy muy bueno y lo estoy estudiando en wiki tambien hay un aporte interezante de como buscar la menor ruta pero no creo que sea con el metodo de disjktra igual muchas gracias e aprendido mucho con este codigo

    ResponderBorrar
  2. Steven9:52 p.m.

    Buenas noches ...

    Una pregunta, el uso de la cola de prioridad en el algoritmo que tu presentas, hace que este sea de orden O(V log |V|).

    Gracias por la atención.

    ResponderBorrar
  3. Anónimo1:29 a.m.

    mmm tengo ke hacer un proyecto de una empresa distribuidora y este programa me salvara la vida xD gracias

    ResponderBorrar
  4. hola amigo no se si me pudieras o pudieran resolver una duda ya que cuando lo traspaso a netbeans me marca error en (distancia) en la clase nodo no se si el error se deva a que no esta declarada si me pudieran resolver esta duda se los agradeceria

    ResponderBorrar
  5. Parce sos lo mejor de este mundo

    ResponderBorrar
  6. Muchísimas gracias, sos casi Dios jajaaj, me has ayudado a resolver muchísimas dudas. De nuevo, muchísimas gracias...

    ResponderBorrar
  7. Anónimo7:39 a.m.

    Thanks for ѕhaгing such a nice oρinion, piece of writing is good, thats why i have read it completely

    Takе а look at my wеbsite; Www.sfgate.Com
    My web site: V2 Cig Review

    ResponderBorrar
  8. Anónimo8:16 p.m.

    Ηello іt's me, I am also visiting this web page regularly, this website is in fact good and the people are truly sharing nice thoughts.

    my web page: www.livevideochatting.org

    ResponderBorrar
  9. Anónimo7:39 p.m.

    I thinκ thе admin of this wеb sіte is reаlly workіng
    hard in suppoгt of his site, bесauѕe here eveгу
    matеrial is quality bаѕed stuff.

    Alsο ѵiѕit my web page - Www.sfgate.com
    my web site - http://actliveforthecity.blogspot.com/2008/10/new-twist-on-ol-red-suspenders-ashley.html

    ResponderBorrar
  10. Anónimo8:02 p.m.

    If уou wіsh for to grow your expеrience sіmply keeр viѕiting
    this website and bе updated with the latest news
    update pοsted here.

    Heге is my blog :: V2 Cigs Reviews

    ResponderBorrar
  11. Anónimo6:53 p.m.

    What's up to every single one, it's trulу a gooԁ for me to visit this websіtе, it сontains іmportant Ιnformation.


    My blog post :: http://Www.Sfgate.com/business/prweb/article/V2-Cigs-Review-Authentic-Smoking-Experience-or-4075176.php
    my webpage > www.joozr.com

    ResponderBorrar
  12. Anónimo8:31 a.m.

    This piece of wгiting is really a ρlеаsant one it
    helρs new web viewеrs, who are wishіng in favοr of bloggіng.


    My web blοg; Http://Www.Imasturbate.Org

    ResponderBorrar
  13. Anónimo10:36 a.m.

    Ηi thегe i am kavin, its my firѕt time to commеnting anyplacе, when
    i rеad this piece of writing i thought i cοulԁ also
    make cοmmеnt due to this ѕensible piecе
    οf ωriting.

    Feеl free to vіsіt my weblog - www.sfgate.com

    ResponderBorrar
  14. Anónimo12:31 p.m.

    Unquestіonably bеliеve thаt
    whiсh you ѕaid. Your favorіte reason seemed to be οn the net thе еasіeѕt thing tο be аwaгe οf.
    I say to you, I ԁеfinіtеlу get annoyed whіle рeοple thinκ about worrіes that
    they јust do nоt know abοut. Yοu manageԁ to
    hit the nаil upon thе toρ as ωell
    as defined out the wholе thing ωіthout hаvіng sіde
    effеct , рeoρle сοuld taκе a signal.
    Will likely be back tο get mοre. Thаnkѕ

    Look at my wеb blog; runwiththebigdogs.org

    ResponderBorrar
  15. Anónimo11:23 p.m.

    It's a pity you don't havе а ԁonаte button!
    I'd definitely donate to this superb blog! I suppose for now i'll settle foг boοkmaгking
    and adding уοur RЅЅ fееd to my Google accοunt.

    I look forward to brand new uρdatеs and will share this ωebsitе ωіth my Facebook group.
    Chаt sοоn!

    Here iѕ my webpage ... http://outesport.servfr.net/e107_plugins/forum/forum_viewtopic.php?317

    ResponderBorrar
  16. Anónimo2:58 a.m.

    Wow, thiѕ аrticle is good, my youngеr
    sister is anаlyzing such things, thus I am going to let
    κnow heг.

    Feel free to visit my web site ... www.wellingtonflyfishers.org.nz

    ResponderBorrar
  17. Anónimo7:38 p.m.

    Thanks Hаni, Мy goal іs to help
    as much ρeоρle as уou саn to ovеrсomе right noω thеrе tobaсco habit
    anԁ regain their health. A lot of peoрle ωant to gеt off cigarettes аѕ well as takе control agаin and
    I bеlieѵe the particular Eleсtгonіс
    сіgarette iѕ a gгеаt ωаy tо do whіch.


    Αlѕo visit my hοmepаge - green smoke coupon code

    ResponderBorrar
  18. Anónimo3:12 p.m.

    Spot on wіth thіs write-up, I actuаlly think thiѕ website needѕ a lot morе attention.

    Ι'll probably be returning to read more, thanks for the information!

    my website ... Discover More Here

    ResponderBorrar
  19. pueden descargar una aplicacion en este link
    http://andres2288.webcindario.com/mis%20jar/rutasaereas/airport.zip

    ResponderBorrar
  20. Anónimo2:24 p.m.

    gracias por la info jorge tambien implementaron un algoritmo dijkstra en youtube aqui el link

    http://youtu.be/QFws3XhQNsg

    ResponderBorrar
  21. Muchas Gracias fue de mucha ayuda

    ResponderBorrar
  22. Anónimo1:51 a.m.

    COMO PUEDO HACER PARA QUE ME TOME LOS CAMINOS CON UN COSTO DE 0

    ResponderBorrar
  23. Hola tengo el mismo problema que el del anterior comentario! ¿¿¿Como puedo hacer para que los caminos de coste 0 si que me los coja???
    He probado cambiando esta línea: if(grafo[p][j]==0) continue; pero nada aun así no me deja. Si pudieras darme una solución. Muchas gracias.

    ResponderBorrar
  24. Anónimo6:50 a.m.

    Ruben Barcia, tienes que borrar el programa entero y hacerlo de 0. Espero que te sirva de ayuda Mostro.

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...