Algoritmo de Dijsktra - Maximizar caminho?

10 de janeiro de 2011 6 respostas

dferrao 10 de janeiro de 2011

Boa noita a todos.

Tenho implementado o algoritmo de Dijsktra em java para me calcular o menor caminho entre 2 cidades:

public ArrayList<Estrada> algoritmoDijkstra(String cidA,String cidB,ArrayList<Cidade> listC,
			ArrayList<Estrada> listE){
		
	    Cidade CInicial = GetCidadeNome(listC, cidA);//vai a lista de cidades buscar um objecto cidade com e
	    Cidade CFinal = GetCidadeNome(listC, cidB);//a string dada por parametro
		int s_inicial = getPosCidade(listC,CInicial); //usamos esta funcao para dada uma cidade retornar
		int s_final = getPosCidade(listC,CFinal);  // o inteiro respectivo no ArrayList<Cidade>
		
		int[] vectEtiquetas = new int[getV()];//Verifica se o vertice ja esta "checado"
		int[] vectCustos = new int[getV()];//custo acumulado
		int[] percursoMinimo = new int[getV()]; //vai ter o percurso minimo de uma cidade a outra
		int w, w0 = 0;//w0 -> posicao do vector onde esta o percurso minimo.
		boolean stop;
		
//-----------------------------------------------------
		
		for (w = 0; w < getV(); w++){//inicializa todas a vareaveis
			vectEtiquetas[w] = -1;
			vectCustos[w] = custo(s_inicial, w);//coloca no vector qual o custo de ir de s_inicial para w
			percursoMinimo[w] = s_inicial;
		}
		
		vectEtiquetas[s_inicial] = s_inicial;//posicao onde comeco a procura
		vectCustos[s_inicial] = 0;//custo inicial e 0
		stop = false;
		
		while (!stop){
			int minimoCusto = INFINITO;
			for (w = 0; w < getV(); w++) {
				if (vectEtiquetas[w] == -1 && (vectCustos[w] < minimoCusto)){//Determina o minimo de todos os vertices k inda nao foram "checados"
					w0 = w;	//diz a posicao onde esta o minimo												//
					minimoCusto = vectCustos[w0];
				}
			}
			if ((minimoCusto == INFINITO) || (s_final == w0)) // Cheguei a sulução!!!
				stop = true;
			
			else{
				vectEtiquetas[w0] = percursoMinimo[w0];
				for (w = 0; w < getV(); w++){
					if (vectCustos[w] > (vectCustos[w0] + custo(w0, w))){ //minimiza o custo
						vectCustos[w] = vectCustos[w0] + custo(w0, w); 
						percursoMinimo[w] = w0; 
					}
				}
			}
		}
		System.out.println("Para ir de "+cidA+" ate "+cidB+" tenho que passar em:");
		int anterior = s_final;
		//apresenta o percurso do fim para o inicio
		ArrayList<Cidade> listAux = new ArrayList<Cidade>();//representara as cidades por onde passo
		listAux.add(CFinal);
		while(anterior != s_inicial){
			anterior = percursoMinimo[anterior];
			listAux.add(listC.get(anterior));
		}
		mostrarListaCidadesPercorridas(listAux);
		ArrayList<Estrada> LE_ondePasso = constroiPercurso(listAux, listE); //Devolve estradas por onde passo
		
		return LE_ondePasso;
	}

Este codigo esta a funcionar a 100%. Como sabem o Dijsktra encrontra o menor caminho dados 2 pontos de uma matriz. Neste momento gostava de saber se existe alguma maneira de, com as devidas alterações, conseguir em vez do caminho minimo, o caminho maximo.

Grato pela atenção,

David Ferrão

6 Respostas

ViniGodoy 10 de jan. de 2011

Na verdade, o algoritmo de Dijsktra encontra todos os menores caminhos entre um determinado ponto e todos os outros pontos do grafo. Ele faz uma busca radial, que pode ser interrompida, caso você queira um caminho só. Mas para um caminho só, é melhor o algoritmo A*.

Não creio que haja algum tipo de busca eficiente para o maior caminho. Você é obrigado a percorrer todos para medi-los.

Adelar 10 de jan. de 2011

Olá,
você pode inverter a lógica nas linhas 30 a 33 e 41 a 44. Não recordo agora se somente alterações nestes pontos resolvem o problema, mas caso queira tentar.

[]'s

ViniGodoy 10 de jan. de 2011

Que eu me lembre a solução não é tão simples. Que eu saiba, você só consegue tempo linear em gráfos acíclicos direcionados.
Vou ver o grande livro verde (amém) do Russel&Norvig aqui em casa para ver se tem algo sobre isso.

Bom, há muita diversão pra quem gosta do problema dos caminhos mais longos nesse artigo.

Sei que quando estava fazendo a API de genéticos pra resolver o algorítmo do caixeiro viajante, acidentalmente inverti a fórmula e também achava caminhos bastante longos, com custo computacional razoável.

dferrao 11 de jan. de 2011

Também estive a pesquisar sobre isso. o problema do dijsktra pra maximização de caminhos, são os ciclos negativos… Por isso penso que este problema não poderá ser resolvido com este algoritmo. Se tiverem novidades digam alguma coisa.

De qualquer forma, obrigado pelas respostas

Adelar 11 de jan. de 2011

dferrao:
Também estive a pesquisar sobre isso. o problema do dijsktra pra maximização de caminhos, são os ciclos negativos… Por isso penso que este problema não poderá ser resolvido com este algoritmo. Se tiverem novidades digam alguma coisa.

De qualquer forma, obrigado pelas respostas

Olá,
vc citou ciclos negativos… lembrei do algorithmo de Bellman-Ford que permite trabalhar com custos negativos. Segue um link http://pt.encydia.com/es/Algoritmo_de_Bellman-Ford

[]'s

Metaleiro 11 de jan. de 2011

Dijkstra.java

import java.io.RandomAccessFile;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

public class routing{
        public static void main( String args[] ){
                routing app = new routing( args[ 0 ] );
        }

        public routing( String inFile ){
                try{
                        RandomAccessFile file = new RandomAccessFile( inFile, "rw" );
                        String tmp = file.readLine(); int i = 0;
                        while( tmp != null ){ tmp = file.readLine(); i++; }

                        file.seek( 0 ); tmp = file.readLine();
                        int graph[][]; graph = new int[ i ][ i ]; i = 0;
                        while( tmp != null ){
                                StringTokenizer sT = new StringTokenizer( tmp, " " ); int j = 0;
                                while( sT.hasMoreTokens() ){ graph[ i ][ j++ ] = Integer.parseInt( sT.nextToken() ); }
                                i++; tmp = file.readLine();
                        }
                        file.close();

                        dijkstra( graph );
                }
                catch( IOException io ){ System.err.println( io.toString() ); System.exit( 1 ); }
                catch( RuntimeException re ){ System.err.println( re.toString() ); System.exit( 1 ); }
        }

        public void dijkstra( int graph[][] ){
                int d[] = new int[ graph.length ];
                int dC[] = new int[ graph.length ];
                int p[] = new int[ graph.length ];
                for( int i = 0; i < graph.length; i++ ){ d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1; }
                d[ 0 ] = 0; dC[ 0 ] = 0;

                int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
                while( i < graph.length ){
                        //extract minimum
                        for( int j = 0; j < dC.length; j++ ){
                                if( min > d[ j ] && dC[ j ] != -1 ){
                                        min = d[ j ]; pos = j;
                                }
                        }
                        dC[ pos ] = -1;

                        //relax
                        for( int j = 0; j < graph.length; j++ ){
                                if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                                        d[ j ] = graph[ pos ][ j ] + d[ pos ];
                                        p[ j ] = pos;
                                }
                        }
                        i++; min = 200;
                }



                for( int j = 0; j < p.length; j++ ){
                        System.out.print( p[ j ] + " " );
                }
                System.out.print( "\n" );
                for( int j = 0; j < d.length; j++ ){
                        System.out.print( d[ j ] + " " );
                }
                System.out.print( "\n" );
        }
}

Criado 10 de janeiro de 2011

Ultima resposta 11 de jan. de 2011

Respostas 6

Participantes 4

6 Respostas

Topicos relacionados