• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Llaverola

algoritmo dijkstra

33 mensagens neste tópico

Junto envio então o codigo em Java do trabalho q estou a fazer, do algoritmo dijkstra..este algoritmo ve o caminho + curto entre duas cidades. so q so estou a conseguir calcular dentro dum vector, temos o nodo start num indice do vector, e calcula-se o nº de caminhos entre TODOS os nodos ou cidades. o k pretendo é: guardar esses caminhos qd temos o nodo destino, para calcular a distancia. EM BAIXO DEIXO TODO O MEU CODIGO FONTE PARA KEM KISER CORRER O PROGRAMA E VER O K ESTE PROGRAMA FAZ. ESTOU A UTILIZAR O JBUILDER2005. por favor, preciso de ajuda. é para um trabalho de faculdade. obrigado

porto - aveiro = 2 ligacoes

lisboa-leiria = 1 ligaçao

coimbra porto = 3 ligacoes

é isto q aparece. e eu quero é ter um nodo partida e destino, calcular o menor caminho entre essas duas cidades e respectiva distancia.

public int[] shortestPathLength(String start) {
            LinkedList linkedList = new LinkedList(); //Criar uma lista ou fila
            Nodo[][] adj = this.adjacencias(); // Matriz das adjacencias dum determinado nodo
            int n = this.nodos.size(); // Numero total de nodos
            int comp[] = new int[n]; // vector que recebe o nº de caminhos entre org e dest
            Nodo nodoStart = this.getNodo(start); // Nodo prim
            int indexStart = (int) nodoStart.id; //indice do nodo start (O ID) no vector nodos

            // esta a inicializar todas as posiçoes do vector comp a infinito
            for (int d = 0; d < comp.length; d++) {
                comp[d] = (int) Math.pow(2, 32);
            }
            comp[indexStart] = 0; // poe o comp[prim] a zero

            linkedList.addFirst(nodoStart); //adicionar o nodostart a lista

            while (!linkedList.isEmpty()) { //enquanto a fila nao esta vazia
                Nodo nodoCur = (Nodo) linkedList.removeFirst(); //removemos o 1º elemento da fila = NODO CURRENTE
                int idCur = (int) nodoCur.id; // o ID do nodo currente
                int prox = 0; //
                Nodo temp = adj[this.nodos.indexOf(nodoCur)][prox]; //indice do nodo currente no vector nodos
                //
                while (temp != null) {
                    int val = (int) temp.id; //nodo temp tem um endereço...
                    if (comp[val] == (int) Math.pow(2, 32)) { //nº inteiro maximo ou seja, infinito
                        comp[val] = comp[idCur] + 1;
                       // this.caminhos.addElement(temp);
                        // ciclo para contar distacia

                       for (int s = 0; s < this.ligacoes.size(); s++) {
                            Ligacao l = (Ligacao)this.ligacoes.elementAt(s);
                           
                        }

                        linkedList.addLast(temp); //adicionar a lista o nodo temp
                    }
                    temp = adj[this.nodos.indexOf(nodoCur)][++prox];
                    //for (int k =0;k<this.caminhos.size();k++){

                }
            }


            return comp;
}


        //*******************MATRIZ DOS NODOS ADJACENTES**************************//

        public Nodo[][] adjacencias() {
            Nodo[][] adj = new Nodo[this.nodos.size()][this.nodos.size()];
            String path[] = new String[20];

            System.out.println("adjacencias(): adj.length = " + adj.length); // numero de nodos

            for (int n = 0; n < this.nodos.size(); n++) { //percorre o vector nodos
                Nodo nodoCur = (Nodo)this.nodos.elementAt(n); // procura o nodoCur no vector nodos
                Vector ligacoes = nodoCur.getLigacoes();


                //imprimir o nº de ligaçoes para cada nodo
                System.out.println("adjacencias(): nodoCur = " +
                                   nodoCur.getCidade() + " ligacoes = " +
                                   ligacoes.size());



                for (int l = 0; l < ligacoes.size(); l++) {
                    Ligacao lig = (Ligacao) ligacoes.elementAt(l);
                    
                    adj[n][l] = lig.getNodoTo();

                    String t = nodoCur.getCidade();
                    String y = lig.getNodoTo().cidade;

                    //IMPRIME LIGAÇOES PARA CADA NODO
                    System.out.println(t+" ---> "+y);
                    
                }
            }
            return adj; //imprime as adjacencias
        }
    }

     

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

a versão que tenho para delphi calcula o menor percurso... se quiseres que o coloque cá para analizares, é só dizeres...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não conheço o algoritmo, se poderem colocar uma versão sempre se "pode dar uns toques".

Não percebi bem o problema, ou melhor a dúvida...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

EM CIMA ESTA O CODIGO DO DIJKSTRA....mas saquem o ficheiro q disponibilizo aí em rar, e corram no computador. e vejam se me ajudam por favor

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

...eu quero é ter um nodo partida e destino, calcular o menor caminho entre essas duas cidades e respectiva distancia.

a versão em delphi faz exactamente isso e está em anexo... analiza e vê o que necessitas de alterar... eu não ajudo porque não percebo um boi de java...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O ano passado tive de fazer uma coisa semelhante, mas usei o IDE Netbeans com a ajuda de duas bibliotecas (JGraph e JGraphT). Pesquisa no google por esses nomes pode ser que te ajude.  :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

versao em delphi é em C right? mas keria era mesmo q alguem corresse o meu programa, e visse o k me falta :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

VA LA PESSOAL....preciso mm entregar esse trabalho em condiçoes. a interface é facil. o problema é com o codio q tenho em cima, guardar os nodos ou ligacoes do nodoTO() = nodo destino...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

é um pouco complicado entender o código e corrigir os erros sem conhecermos bem os dados do problemas e a forma como estão armazenados.

para ajudar as coisas o teu post inicial está num português pouco legível.

se percebi bem a tua dúvida, tens o array que usaste no algoritmo e queres extrair o caminho. deve começar no nodo de destino e associado ao nodo de destino devias ter guardado o nodo que te permitiu lá chegar, desta forma consegues determinar o anterior, e depois o anterior ao anterior, etc. até que chegas à origem.

estou a assumir que guardaste ao longo do algoritmo esse tal array auxiliar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

versao em delphi é em C right? mas keria era mesmo q alguem corresse o meu programa, e visse o k me falta :S

delphi é mais pascal...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, eu estava a tentar ajudar mas isto está a ser complicado...

Tenho o código dele, é o que também esta colocado em anexo, mas o que a implementação que ele tem faz é calcular o "custo do caminho mais curto" e não o "caminho mais curto". O método recebe apenas um parâmetro, o ponto de origem, e diz quantos saltos é preciso dar para atingir todos os nós existentes. Não guarda qualquer informação dos nós por onde passou ou mesmo o caminho que tomou....

A dúvida dele é como introduzir nisto tudo o ponto destino... tou de volta do código à uma boa hora e não saco nada do que aqui está... alguém tem umas luzes?

Já agora marinheiro, o código é pouco legível, já não estou habituado a pascal :thumbsup:.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

já somos dois :thumbsup: :thumbsup: :D

eu dei a volta a alguns pormenores desse projecto há uns tempos largos, mas já não sei onde tenho uma folha em que tinha todas as conclusões que tinha tirado sobre o que representavam as variáveis e o que as rotinas faziam... já dei voltas à minha pasta dos projectos e não encontro em lado nenhum...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o meu problema é que não me consigo entender no código do Llaverola, as variáveis não têm nomes sugestivos, as estruturas de dados não guardam dados que são precisos e os objectos possuiem uns atributos que não percebo bem. Estive a ver o algoritmo na wikipedia e fazia isto de forma diferente...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se ele introduzir o ponto de destino, pode parar o ciclo quando chegar a esse ponto em vez de continuar até a lista ficar vazia (isto porque o grafo não tem pesos negativos).

PS: parece-me que isto é mais uma travessia em largura do grafo do que o algoritmo de dijsktra... embora acabe por ser um caso particular do algoritmo de dijsktra, mas bem mais simples.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que ele quer é mesmo saber o caminho mais curto entre dois pontos, e ai penso que se inclua bem no algoritmo mas não é isso que ele está a fazer, pelo menos pelo que estou a ver... e não consigo colocar o código dele a fazer correctamente o algoritmo de dijsktra, não tenho experiência suficiente com o algoritmo para em tão pouco tempo mudar o que está feito... bem vou continuar a olhar para o código dele e ver se descurtino alguma coisa de jeito....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só uma coisa, são capazes de me arranjar o algoritmo em pseudo-código que não seja chinês? com coisas mais significativas que "Set Q" e "w, s , v"... para ver se estou a perceber bem isto. Encontrei uns na net mas a pequisa só mostrava código e não queria código...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

penso que as alterações que fiz devem resolver mais ou menos o problema... provavelmente ainda existem alguns erros de tipos, mas a ideia penso que está correcta (tendo em conta que tenho tempo para entender a representação do grafo e a parte que já estava feita, não garanto que funcione!).

o código que adicionei é o que não está indentado.

EDIT: assumi que o ciclo pára quando chega ao destino, coisa que neste momento ainda não está a acontecer (aliás, onde é que está o destino?)

public int[] shortestPathLength(String start) {
            LinkedList linkedList = new LinkedList(); //Criar uma lista ou fila
            Nodo[][] adj = this.adjacencias(); // Matriz das adjacencias dum determinado nodo
            int n = this.nodos.size(); // Numero total de nodos
            int comp[] = new int[n]; // vector que recebe o nº de caminhos entre org e dest
            Nodo nodoStart = this.getNodo(start); // Nodo prim
            int indexStart = (int) nodoStart.id; //indice do nodo start (O ID) no vector nodos


int [] prev=new int[<numero de nodos>]; //assumo que todos os nodos sejam representados por inteiros
for(int i=0;i<...;i++) prev[i]=-1;



            // esta a inicializar todas as posiçoes do vector comp a infinito
            for (int d = 0; d < comp.length; d++) {
                comp[d] = (int) Math.pow(2, 32);
            }
            comp[indexStart] = 0; // poe o comp[prim] a zero

            linkedList.addFirst(nodoStart); //adicionar o nodostart a lista

            while (!linkedList.isEmpty()) { //enquanto a fila nao esta vazia
                Nodo nodoCur = (Nodo) linkedList.removeFirst(); //removemos o 1º elemento da fila = NODO CURRENTE
                int idCur = (int) nodoCur.id; // o ID do nodo currente
                int prox = 0; //
                Nodo temp = adj[this.nodos.indexOf(nodoCur)][prox]; //indice do nodo currente no vector nodos
                //
                while (temp != null) {
                    int val = (int) temp.id; //nodo temp tem um endereço...
                    if (comp[val] == (int) Math.pow(2, 32)) { //nº inteiro maximo ou seja, infinito
                        comp[val] = comp[idCur] + 1;
                       // this.caminhos.addElement(temp);
                        // ciclo para contar distacia

                       for (int s = 0; s < this.ligacoes.size(); s++) {
                            Ligacao l = (Ligacao)this.ligacoes.elementAt(s);
                           
                        }


if(prev[temp.id]==-1) prev[temp.id]=nodoCur.id;


                        linkedList.addLast(temp); //adicionar a lista o nodo temp
                    }
                    temp = adj[this.nodos.indexOf(nodoCur)][++prox];
                    //for (int k =0;k<this.caminhos.size();k++){

                }
     }

caminho=new LinkedList();
while(int x!=-1)
{
caminho.addFirst(temp.id);
x=prev[temp.id];
}


return comp;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que ele quer é mesmo saber o caminho mais curto entre dois pontos, e ai penso que se inclua bem no algoritmo mas não é isso que ele está a fazer, pelo menos pelo que estou a ver...

o algoritmo de dijsktra é para casos em que tens grafos pesados e queres encontrar o caminho mais curto em função desses pesos. neste caso, pelo que percebi, só lhe interessa o caminho que passe por menos nodos, por isso pode fazer uma travessia por níveis do grafo (que se resume a uma travessia em largura) e tem o problema resolvido. repara que ele adiciona sempre os novos nodos ao fim da lista e remove no início, no algoritmo de dijsktra nem sempre se pode remover o do início.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se reparares atraves do comp, sei q do nodostart ate a um determinado nodoTo com indice x no vector nodos, sabemos qts caminhos temos, n sabemos é quais. o problema é esse. o k eu acho é q, enquanto ele esta a somar os caminhos deviamos guardar os mesmos. por exemplo:

no vector comp temos [0,1,1,2,3,7]

o nosso nodoStart tem indice 0 no vector nodos, ja q o seu indice tb é zero no vector comp certo?

sabemos entao q do nodo com indice 0, ate ao nodo q se encontra por exemplo na posição 3 do vector, tem 2 caminhos. certo?

o problema é: como guardar esses caminhos? sera q cada posiçao do vector comp tera de apontar para um array ou guardamos as respectivas ligacoeS?

se houver outra forma de fazer o algoritmo, e se alguem mo conseguir fazer, agradecia ja q estou com dificuldades. em cima, tem la o codigo fonte...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

já viste as alterações que fiz ao teu código?

com uma ou outra alteração já deve resolver o problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ola rui. sim ja vi, mas ta-me a dar erros. conseguiste correr o programa com esse codigo? alem disso, n percebi mt bem o k fizeste

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ola rui. sim ja vi, mas ta-me a dar erros. conseguiste correr o programa com esse codigo? alem disso, n percebi mt bem o k fizeste

eu avisei que ainda devia ter alguns erros, mas a ideia devia estar correcta.

o que eu fiz foi criar um array para guardar o nodo que permite chegar a outro.

para o grafo em anexo terias este array:

1 -> -1 //é a origem

2 -> 1 //para chegar ao 2, vens do 1

3 -> 1 //para chegar ao 3, vens do 1

4 -> 3 //para chegar ao 4, vens do 3

5 -> 3 //...

6 -> 2

7 -> 5

8 -> 7

ou seja, antes do 8 tinhas o 7, antes do 7 tinhas o 5, etc. o que te permitia chegar ao caminho 1-3-5-7-8

PS: fiz uma correcção no código que tinha colocado anteriormente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

humm

ja percebi a tua ideia. NAO CONSEGUI FAZER O DOWNLOAD DO TEU FICHEIRO EM ANEXO, dá erro....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ja agora rui, repara q no codigo, so imprimimos o nodoStart, ONDE ENTRA O NODO DESTINO?

estou mm com mts duvidas e n sei o k fazer no codigo :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

RUI DEIXO O MEU CODIGO COMPLETO DO MEU PROGRAMA...faz o download do ficheiro em anexo la em cima e ve o k consegues fazer por favor..estou mm a precisar de ajuda nisto :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora