1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Algoritmo de Dijkstra em Java

Discussão em 'Programação' iniciada por OubeLa, 25 de Abril de 2008. (Respostas: 8; Visualizações: 16447)

  1. OubeLa

    OubeLa Power Member

    Tenho de implementar este algoritmo mas estou com alguns problemas


    Código:
    //Função que determina o menor caminho possível entre duas cidades - a flag servirá para indicar se o caminho a calcular é o melhor em distância (true) ou tempo(false)
        public ArrayList<Cidade> menorCaminho(Cidade origem, Cidade destino, boolean flag)
        {
            
            if (origem.getN() == destino.getN())
                throw new IllegalArgumentException("Cidade de origem igual 'a cidade de destino");
            
            Cidade menor = null, actual = null;
            
            //O menor caminho começa com a origem
            cidades_minimo.add(origem);
            
            actual = origem;
            //inicializa todas as cidades
            Iterator<Cidade> it = cidades.iterator();
            while (it.hasNext())
            {
                Cidade cidade = (Cidade) it.next();
                if(flag == true) {
                    if (cidade.getN() == actual.getN()) {
                        actual.setDistancia(0);
                        cidade = actual;
                    }
                
                    else
                        cidade.setDistancia(infinito);        //a distância a cada cidade é infinita por defeito
                }
                
            //    else 
                //    cidade.setTempo(infinito);
                
                cidade.setAnterior(null);
            }
                    
            actual = origem;                    //inicialmente a cidade actual é a cidade origem
            
            
    
            
            //procura as cidades vizinhas à origem
            ArrayList<Cidade> adjacentes = actual.getCidadesVizinhas();
            
            
            //caso não existam cidades vizinhas, não existe nenhum caminho possível
            try
            {
                if (adjacentes == null)
                    throw new IllegalArgumentException("Nao existe nenhum caminho possivel");
            
                else
                {
                    //caso contrário, as vizinhas são definidas como as cidades anteriores da origem
                    it = adjacentes.iterator();
                    while (it.hasNext())
                    {
                        Cidade cidade = (Cidade)it.next();
                        cidade.setAnterior(origem);
                    }
                    
                    //Aqui começa verdadeiramente o algoritmo
                    
                    //Enquanto a cidade actual não for a cidade de destino
                    while (actual.getN() != destino.getN())    
                    {
                        ArrayList<Cidade> adjacentes_aux = new ArrayList<Cidade>();
                        //a menor alternativa, caso inicial
                        menor = null;            
                        
                        for (int i = 0; i < cidades.size(); i++)
                        {
                            if (existe((cidades.get(i)).getN()) == false)                //se a cidade ainda não tiver sido visitada
                            {
                                if (menor == null)                            //para o caso inicial, menor é a primeira cidade da lista
                                    menor = cidades.get(i);
                                
                                Cidade c = cidades.get(i);    //c é a cidade em análise
                                
                                
                                if (actual.getCidadesVizinhas() == null)
                                    throw new IllegalArgumentException("Nao existe nenhum caminho possivel");
                            
                                if (actual.getCusto(c) == 0) {
                                    ++i;
                                
                                    continue;
                                }
                                
                                //se a distância à cidade anterior + o custo da cidade em análise for menor que a distância à anterior da cidade em análise
                                //e se a cidade já tiver sido inicializada
                       /*AQUI*/         if (actual.getPeso(flag) + actual.getCusto(c) < actual.getPeso(flag))
                                { 
                                    if (actual.getCusto(c) < infinito) {
                                    //muda a distância da cidade actual para a distância "optimizada"
                                    if(flag == true)
                                        c.setDistancia(actual.getPeso(flag) + actual.getCusto(c));
                                    else 
                                        c.setTempo(actual.getPeso(flag) + actual.getCusto(c));
                                    }
                                    
                                    if (actual.getCusto(c) < infinito)
                                        c.setAnterior(actual);
                                }
                                if (c.getPeso(flag) < menor.getPeso(flag)) //se a distância da cidade actual for menor do que até agora foi considerada menor, menor passa a ser c
                                    menor = c;
                            }
                        }
                        actual = menor;        //a cidade em análise no próximo ciclo passa a ser a menor encontrada no ciclo for anterior
                        cidades_minimo.add(actual);        //e é adicionada à lista do menor caminho
                    }
            
                    //ArrayList para guardar o menor caminho
                    ArrayList<Cidade> minimo = new ArrayList<Cidade>(cidades_minimo.size());
                    //Define o último nó do menor caminho como o actual
                    actual = cidades_minimo.get(cidades_minimo.size()-1);
                    
                    //Insere na pilha todos os elementos do menor caminho para ordenar
                    while (actual != null)
                    {
                        minimo.add(0,actual);
                        actual = actual.getAnterior();
                    }
            
                    cidades_minimo = minimo;
                    
                    return minimo;
                
                }
            }
            
            catch (IllegalArgumentException e)
            {
                System.err.println(e.getMessage());
                return null;
            }
        }
    O algoritmo funciona bem no caso de ser um grafo assim.

    Código:
    ArrayList<Cidade> Cidades = new ArrayList<Cidade>();
            
            Cidade SMI = new Cidade("S.Mamede Infesta");
            Cidades.add(SMI);
            
            Cidade Custoias = new Cidade("Custóias");
            Cidades.add(Custoias);
            
            new Estrada(SMI,Custoias,3);
            
            Cidade Balio = new Cidade("Leça do Balio");
            Cidades.add(Balio);
            
            new Estrada (Custoias,Balio,2);
            
            Cidade Hora = new Cidade("Senhora da Hora");
            Cidades.add(Hora);
            
            new Estrada(Custoias,Hora, 3);
            new Estrada(Hora, Balio,4);
            
            origem = SMI;
            destino = Balio;
    Cria-se o objecto algoritmo, e faz-se

    Código:
    alg.caminhoMaisCurto(Origem, Destino, flag)
    No caso de ser algo mais elaborado, tipo isto

    1 2 803
    2 1 803
    2 3 12
    3 4 158
    2 4 10000
    4 3 158

    Em que a primeira coluna e segunda coluna são cidades, e a terceira é a distancia entre cidades.

    No caso de se querer ir da cidade 1 para a cidade 4, o caminho correcto seria: 1 - 2 - 3 - 4

    O problema é que lança uma excepção: NullPointerException neste código (que é originada no próprio algoritmo (procurar onde está comentado/*AQUI*/))

    Código:
    // Função que devolve o peso da estrada (em que o peso pode ser a distância ou tempo) que une a cidade à cidade de destino da mesma
        public int getCusto(Cidade destino)
        {    
            for (int i = 0; i < estradas.size(); i++)
            {
                Estrada estrada = estradas.get(i);
                
            //se a origem for esta cidade e o destino da estrada for a cidade dada como argumento ou vice versa
               /*AQUI*/ if ((estrada.getOrigem().getN() == this.nCidade && estrada.getDestino().getN() == destino.getN()) 
                        || 
                        (estrada.getOrigem().getN() == destino.getN() && estrada.getDestino().getN() == this.nCidade))
                {
                    return estrada.getPeso();
                }
                
                //else
                    //return Integer.MAX_VALUE;
            
            }
            
            return Integer.MAX_VALUE;    //se não se verificar a condição anterior, devolve infinito, que é o valor por defeito considerado no algoritmo de Dijkstra
        }
    
    Provavelmente é o o algoritmo que está mal implementado. Se alguém conseguir dar uma ajudinha agradecia ;)
     
    Última edição: 25 de Abril de 2008
  2. Boo

    Boo

    Bem.. com essa quantidade enorme de codigo.. suponho q maior parte das pessoas vai ficar tao intimidada que nem te responde lol

    Eu tb nao sou diferente e tb nao tenho grande paciencia pa tar a ver isso tudo por isso vou te deixar algumas dicas que talvez te possam ajudar.

    Primeiro, o algoritmo de dijkstra nao calcula o caminho mais curto entre dois pontos, mas sim uma arvore do caminho mais curto de qq vertice até ao de origem. Depois desse calculo é que podes pegar na arvore e tirar o caminho até ao vertice destino que te interessa.

    Segundo, este algoritmo é relativamente simples.. e nao necessita de tantas linhas de codigo como as que tu gastaste.. suponho que tas a complicar mesmo muito...

    O que eu te aconselho é que te informes melhor sobre o algoritmo aí pela net. Deves encontrar sites com animações e assim que mostram o funcionamento passo a passo, e assim concerteza passavas para codigo bastante mais eficaz.

    Se quiseres insistir no código que tens feito.. posso tentar mandar uma posta meio à sorte de qual será o teu problema, visto que eu tb só passei os olhos pelo código mt diagonalmente.
    Parece-me que o teu algoritmo está a parar qnd encontra o vertice destino! Issp não pode ser feito.. visto que chegares ao vertice destino nao implica que chegaste a ele pelo caminho mais curto, pode haver um caminho "à volta" mais curto do que o que utilizaste. Mas lá está.. isto faz parte da noção de que o algoritmo não vai atrás dum vertice em particular onde parar.. é mesmo suposto percorrer o grafo todo e calcular todos os caminhos mais curtos.
     
  3. OubeLa

    OubeLa Power Member

    Obrigado pelo reply, mas afinal já consegui, o problema afinal não era o algoritmo mas sim uma função de leitura de um ficheiro txt. De qualquer forma, terei de melhorar o algoritmo porque está bastante lento.
     
  4. esse algoritmo n ta um bocado complexo??
    tenho um programa de uma rede ferroviaria feita com um grafo e varias estacoes e preciso de calcular o caminho mais curto desde a estacao origem de um comboio ate a estacao de chegada e nao tou a conseguir entender bem esse codigo...n ha maneira mais simples...se puderem dar uma ajuda agradecia lol
     
  5. AliFromCairo

    AliFromCairo Power Member

    Vê se percebes melhor o pseudo-código que se encontra aqui.
     
  6. epa eu ja tinha lido isso mas fiquei na mesma :S :S n ha ninguem q consiga msm explicar como, por exemplo, criar a tabela, para saber o caminho mais curto?
     
  7. blueomega

    blueomega Power Member

    a primeira vista parece um by the book dijkstra (ha coisa de 2 anos fiz algo similar com linhas de comboio) e fiz um a star na semana passada, saltam algumas coisas a vista

    o não uso de uma priority queue (criterio de ordenação é a distancia do ponto inicial ao mesmo), simplificava em muito o no a expandir

    deixo aqui o meu esquema simplificado do a star

    [​IMG]

    o funcionamento é o seguinte (ter em conta que no a star uso uma open list e uma closed list)

    adiciono o no inicial a fila de prioridade, verefico se é o final.

    se não for gero os sucessores (os adjacentes, o trabalho tinha umas coisas especiais)

    se ja esta na lista de nos visitados, mas a sua distancia for novo caminho for inferior altero o pai do mesmo

    senão adiciono a lista de nos a visitar

    puxo de novo o que esta na cabeça da lista e verefico de novo


    deve dar pra adaptar
     
  8. JIMYSPEED

    JIMYSPEED Power Member

    Boas

    ja agora podes me dizer como estas a ler do ficheiro txt que metodo tas a usar
    e ja agora o formato dos dados que tens dentro do txt

    cumps
     
  9. sounabo

    sounabo Power Member

    Isso é geral para qualquer algoritmo de procura...
    Se aconselhas a usar, então é melhor explicares as regras desse esqueleto:
    - a acção "add successor to open list", mais concretamente, a forma como se adiciona é que define o tipo de procura: no fim, é breadth-first search, no início é depth-first search, ordenado pelo valor da heurística é best-first search, ordenado pelo valor total estimado (heurística mais "cost-so-far") é que é A*, and so on...

    A nível de implementação, há vários outros pormenores a ter em conta, como o que disseste:
    "... se ja esta na lista de nos visitados, mas a sua distancia for novo caminho for inferior altero o pai do mesmo ..."
    Atenção que é necessário olhar também para a lista de nós a visitar e mudar o pai, caso a estimativa total seja tb inferior.
     

Partilhar esta Página