O clássico e complicado dijkstra

4 respostas
guisantogui

Galera empaquei na implementação do dijkstra, segue o código que eu tenho implementado:

private Nodo<E> extractMin(List<Nodo><E>> fila){
        Nodo<E> min = fila.get(0);
        for(Nodo<E> n: fila){
            if((Integer)min.getItem() > (Integer)n.getItem()){
                min = n;
            }
        }
        return min;
    }
    
    private int[] initDj(Nodo<E> n){
        int[] init = new int[nodos.size()];
        for(int i = 0;i < init.length; i++){
            if(nodos.get(i).equals(n)){
                init[i] = 0;
            }
            else{
                init[i] = Integer.MAX_VALUE;
            }
        }
        return init;
    }

    public void dijkstra(E origem) {
        Nodo<E> org = procuraNodo(origem);
        Nodo<E> aux = null;
        List<Nodo><E>> fila = new ArrayList<Nodo><E>>(nodos.size());
        int[] dist = initDj(org);
        if(org != null){
            fila.add(org);
            while(!fila.isEmpty()){
                aux = extractMin(fila);
                fila.remove(aux);
                for(int i = 0; i < nodos.size(); i++){
                    if(aux.getAdjacentes().contains(nodos.get(i)) && fila.contains(nodos.get(i))){
                        
                    }
                }
            }
        }
    }

PS.: Usei List por que não tava com saco de ficar implementando uma Queue, nas férias eu faço uma fila bonitinha ;)

4 Respostas

ViniGodoy

Toda linked list, no Java, é uma Queue:

Queue<Nodo> fila = new LinkedList<Nodo>();

http://download.oracle.com/javase/6/docs/api/java/util/Queue.html

guisantogui

Bom vinny, mas eu preciso de uma PriorityQueue que eu sei que também tem no java, mas na real não é esse o problema, eu me quebrei foi nessa parte do pseudo código, depois vou dar uma olhada melhor afinal eram mais de duas da manhã ontem, agradeço a força!

PSEUDO-CÓDIGO (que viria após a implementação do último “if”

então d[v] ← d[u] + w(u, v) π[v] ← u

R

não entendi sua duvida

essa parte que vc tem dúvida é quase igual a parte que está acima dela no pseudocódigo com a diferença que ele atribui o valor em uma variavel que antes era nula ( π[v] )

para cada v adjacente a u se d[v] > d[u] + w(u, v) //relaxe (u, v) então d[v] ← d[u] + w(u, v) π[v] ← u

guisantogui

Eu to com problemas é em passar o pseudo código para java usando aquela minha estrutura! :confused:

Criado 25 de junho de 2011
Ultima resposta 25 de jun. de 2011
Respostas 4
Participantes 3