Dijkstra (menor caminho)

Pelas caridades,

alguem tem o algoritmo de Dijkstra implementado? Ou um outro algoritmo qualquer que calcule o menor caminho entre dois nós?

jah existe essa pergunta no forum… procura ae

http://www.portaljava.com.br/home/modules.php?name=Forums&file=search&mode=results&sid=727443779f3e8d068d72c663a61022f0

SEu link não ajudou em nada o colega que precisava de ajuda.Alias tive a liberdade de procurar o tema "dijkstra e não encontrei nada que pudesse ajuda-lo…

http://www.portaljava.com.br/home/modules.php?name=Forums&file=viewtopic&t=20387&highlight=dijkstra&sid=7c458677648130d5ef6d07df2ae63f15

SEu link não ajudou em nada o colega que precisava de ajuda.Alias tive a liberdade de procurar o tema "dijkstra e não encontrei nada que pudesse ajuda-lo…[/quote]

Cara, qual é a sua? Pode ser que não ajudou, mas eu não respondi para você, respondi para quem iniciou o tópico. Portanto, vale a boa intenção. Aliás, alguém perguntou para você alguma coisa se você teve a liberdade de procurar algo sobre o tema? Minha intenção foi ajudar, se não ajudou o problema não é seu, então sai fora

Calma, gente. vamos com calma.

Eu juro q já tinha procurado antes. Talvez nao tenha usadas as palavras certas.

Bom, na resposta tinha orientacao de como procurar no google:
“shortest path” Java

Também já tinha procurado, mas em portugues.

Um dos links é esse:
http://renaud.waldura.com/doc/java/dijkstra/

Foi o que achei mais claro pra implementar.
Na Net tá cheio de codigos, mas a grande maioria eh applet.

Seguindo o algoritmo q tem nessa pagina aí, consegui fazer isso:

/*
 * Created on 27/06/2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
//package br.com.mundojava.desafio3;
package acm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author adorilson
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class CaminhoMinimo implements SimuladorDeCaminhoMinimo {
	
	private double[][] grafo; // e o proprio grafo
	private int qtde; // qtde de nos
	
	private int[] pi; // predecessor de cada vertice com menor caminho
	private double[] d; // menor caminho para cada vertice a partir da fonte
	List S; // lista de vertices visitados
	List Q; // lista de vertices nao visitados
	
	private static final int INFINITO = -1;
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#inicializa(int)
	 */
	public void inicializa(int total) {
		total++;
		grafo = new double[total][total];
		qtde = total;
		inicializaGrafo();
	}
	
	private void inicializaGrafo(){
		// fazendo todo mundo ir para o infinito
		for(int de=1; de<qtde;de++){
			for(int para=1; para<qtde; para++){
				if (de==para){
					grafo[de][para]=0;
				}else{
					grafo[de][para]= INFINITO;
				}
				
			}
		}
	}
	
	
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#adicionaConexao(int, int, double)
	 */
	public void adicionaConexao(int de, int para, double custo) {
		this.grafo[de][para] = custo;
	}
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#caminhoMinimo(int, int)
	 */
	
	public double caminhoMinimo(int de, int para) {
		menorCaminho(de);
		return d[para];
	}


	public static void main(String[] args) {
		
		CaminhoMinimo cm = new CaminhoMinimo();
		cm.inicializa(7); //tamanho do grafo
		
		//montando o grafo....
		cm.adicionaConexao(1, 2, 3);		
		cm.adicionaConexao(2, 3, 1);
		cm.adicionaConexao(2, 4, 5);
		cm.adicionaConexao(3, 4, 2);
		cm.adicionaConexao(3, 6, 17);
		cm.adicionaConexao(4, 5, 10);
		cm.adicionaConexao(5, 6, 2);
		cm.adicionaConexao(6, 3, 17);
		cm.adicionaConexao(3, 1, 5);
		cm.adicionaConexao(7, 5, 2);
		cm.adicionaConexao(7, 6, 12);
		
		
		int n =3;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =1;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =2;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =4;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =5;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =6;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =7;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		int de = 4;
		int para = 1; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
			cm.caminhoMinimo(de,para));
		
		de = 3;
		para = 1;
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
			cm.caminhoMinimo(de,para));
		
		de = 1;
		para = 3; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
				cm.caminhoMinimo(de,para));
		
		de = 1;
		para = 6; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
				cm.caminhoMinimo(de,para));
	}

	
	
	private void mostraCaminho(){
	  for(int para=1; para<qtde; para++){
	  	System.out.print(d[para] + " ");
	  }
	}
	
	private void menorCaminho(int de){
		
		d = new double[qtde+1];
		
		for (int  i=1; i<qtde; i++) {
			d[i] = INFINITO;
		}
		
		pi = new int[qtde];
		
		S = new ArrayList();
		Q = new ArrayList();
		
		Q.add(new Integer(de));
		
		while (!Q.isEmpty()){
			Object u = extractMinimum(Q);
			S.add(u);
			relaxNeighbors(u);
		}
		
		// nao me pergunte porque, mas isso eh um fator de correção :D
		for(int c=1; c<qtde; c++){
			if (d[c]!=INFINITO){
				d[c]++;
			}
		}
		d[de]=0;
		
	}
	
	private static Object extractMinimum(List Q){
		// localizando o menor da lista
		Integer menor= (Integer)Q.get(0);
		for(int i=1; i<Q.size(); i++){
			Integer atual = (Integer)Q.get(i);
			if (atual.intValue() < menor.intValue()){
				menor = atual;
				
			}
		}
		
		// removendo o menor
		Q.remove(menor);
		
		// retornando o menor
		return menor; 
	}
	
	private void relaxNeighbors(Object u){
		
		//varrendo os adjacentes de u que nao estao em S
		int u1 = ((Integer)u).intValue();
		List vizinhos = getVizinhos(u1);
		
		for(int i=0; i<vizinhos.size(); i++){
			Object v = vizinhos.get(i);
			if(!isVisitado(v)){
				int v1 = ((Integer) v).intValue();
				double tam = d[u1] + grafo[u1][v1];
					if (d[v1]==INFINITO ){
					d[v1] = tam;
					pi[v1] = u1;
					Q.add(v);
				}else{
					if(d[v1] >  tam ){
						d[v1] = tam;
						pi[v1] = u1;
						Q.add(v);
						}
				}
			}
		}
		
		
	}
	
	private boolean isVisitado(Object v){
		boolean result = false;
		int v1 = ((Integer)v).intValue();
		for(int i=0; i<S.size(); i++){
			Integer u = (Integer)S.get(i);
			if(u.intValue()==v1){
				result = true;
				break;
			}
		}
		
		return result;
	}
		
	private List getVizinhos(int u){
		int de = u;
		List v = new ArrayList();
		for(int para=1; para<qtde; para++){
			if(u!=para & grafo[u][para]!=INFINITO){
				v.add(new Integer(para));
			}
		}
		
		return v;
	}
	
}

Passou pelo teste q tem no main() da classe. Mas nao pelo teste do juiz online da revista mundojava :sad:

Qm tiver afim de depurar e achar o erro, a comunidade agradece.[/quote]

/*
 * Created on 27/06/2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
//package br.com.mundojava.desafio3;
package acm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author adorilson
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class CaminhoMinimo implements SimuladorDeCaminhoMinimo {
	
	private double[][] grafo; // e o proprio grafo
	private int qtde; // qtde de nos
	
	private int[] pi; // predecessor de cada vertice com menor caminho
	private double[] d; // menor caminho para cada vertice a partir da fonte
	List S; // lista de vertices visitados
	List Q; // lista de vertices nao visitados
	
	private static final int INFINITO = -1;
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#inicializa(int)
	 */
	public void inicializa(int total) {
		total++;
		grafo = new double[total][total];
		qtde = total;
		inicializaGrafo();
	}
	
	private void inicializaGrafo(){
		// fazendo todo mundo ir para o infinito
		for(int de=1; de<qtde;de++){
			for(int para=1; para<qtde; para++){
				if (de==para){
					grafo[de][para]=0;
				}else{
					grafo[de][para]= INFINITO;
				}
				
			}
		}
	}
	
	
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#adicionaConexao(int, int, double)
	 */
	public void adicionaConexao(int de, int para, double custo) {
		this.grafo[de][para] = custo;
	}
	
	/* (non-Javadoc)
	 * @see acm.SimuladorDeCaminhoMinino#caminhoMinimo(int, int)
	 */
	
	public double caminhoMinimo(int de, int para) {
		menorCaminho(de);
		return d[para];
	}


	public static void main(String[] args) {
		
		CaminhoMinimo cm = new CaminhoMinimo();
		cm.inicializa(7); //tamanho do grafo
		
		//montando o grafo....
		cm.adicionaConexao(1, 2, 3);		
		cm.adicionaConexao(2, 3, 1);
		cm.adicionaConexao(2, 4, 5);
		cm.adicionaConexao(3, 4, 2);
		cm.adicionaConexao(3, 6, 17);
		cm.adicionaConexao(4, 5, 10);
		cm.adicionaConexao(5, 6, 2);
		cm.adicionaConexao(6, 3, 17);
		cm.adicionaConexao(3, 1, 5);
		cm.adicionaConexao(7, 5, 2);
		cm.adicionaConexao(7, 6, 12);
		
		
		int n =3;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =1;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =2;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =4;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =5;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =6;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		n =7;
		System.out.println(n);
		cm.menorCaminho(n);
		cm.mostraCaminho();
		System.out.println("\n");
		
		int de = 4;
		int para = 1; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
			cm.caminhoMinimo(de,para));
		
		de = 3;
		para = 1;
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
			cm.caminhoMinimo(de,para));
		
		de = 1;
		para = 3; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
				cm.caminhoMinimo(de,para));
		
		de = 1;
		para = 6; 
		System.out.println("Menor caminho entre: " + de + " e " + para + " é: " + 
				cm.caminhoMinimo(de,para));
	}

	
	
	private void mostraCaminho(){
	  for(int para=1; para<qtde; para++){
	  	System.out.print(d[para] + " ");
	  }
	}
	
	private void menorCaminho(int de){
		
		d = new double[qtde+1];
		
		for (int  i=1; i<qtde; i++) {
			d[i] = INFINITO;
		}
		
		pi = new int[qtde];
		
		S = new ArrayList();
		Q = new ArrayList();
		
		Q.add(new Integer(de));
		
		while (!Q.isEmpty()){
			Object u = extractMinimum(Q);
			S.add(u);
			relaxNeighbors(u);
		}
		
		// nao me pergunte porque, mas isso eh um fator de correção :D
		for(int c=1; c<qtde; c++){
			if (d[c]!=INFINITO){
				d[c]++;
			}
		}
		d[de]=0;
		
	}
	
	private static Object extractMinimum(List Q){
		// localizando o menor da lista
		Integer menor= (Integer)Q.get(0);
		for(int i=1; i<Q.size(); i++){
			Integer atual = (Integer)Q.get(i);
			if (atual.intValue() < menor.intValue()){
				menor = atual;
				
			}
		}
		
		// removendo o menor
		Q.remove(menor);
		
		// retornando o menor
		return menor; 
	}
	
	private void relaxNeighbors(Object u){
		
		//varrendo os adjacentes de u que nao estao em S
		int u1 = ((Integer)u).intValue();
		List vizinhos = getVizinhos(u1);
		
		for(int i=0; i<vizinhos.size(); i++){
			Object v = vizinhos.get(i);
			if(!isVisitado(v)){
				int v1 = ((Integer) v).intValue();
				double tam = d[u1] + grafo[u1][v1];
					if (d[v1]==INFINITO ){
					d[v1] = tam;
					pi[v1] = u1;
					Q.add(v);
				}else{
					if(d[v1] >  tam ){
						d[v1] = tam;
						pi[v1] = u1;
						Q.add(v);
						}
				}
			}
		}
		
		
	}
	
	private boolean isVisitado(Object v){
		boolean result = false;
		int v1 = ((Integer)v).intValue();
		for(int i=0; i<S.size(); i++){
			Integer u = (Integer)S.get(i);
			if(u.intValue()==v1){
				result = true;
				break;
			}
		}
		
		return result;
	}
		
	private List getVizinhos(int u){
		int de = u;
		List v = new ArrayList();
		for(int para=1; para<qtde; para++){
			if(u!=para & grafo[u][para]!=INFINITO){
				v.add(new Integer(para));
			}
		}
		
		return v;
	}
	
}

Passou pelo teste q tem no main() da classe. Mas nao pelo teste do juiz online da revista mundojava :sad:

Qm tiver afim de depurar e achar o erro, a comunidade agradece.[/quote][/quote]

I ae rapaz!! Blz?
Cara eu queria compilar este codigo, mais acho que preciso do
< package br.com.mundojava.desafio3; >
pois esta dando um erro logo na primeira linha:

  1. –> class CaminhoMinimo implements SimuladorDeCaminhoMinimo {

A menssagem de erro é (" cannot find symbol "), deve ser pq eu preciso do package?

se vc tiver ai e puder me mandar, vai meu email ai:
thompsondv@gmail.com

vlw!

[quote=“adorilson”]Pelas caridades,

alguem tem o algoritmo de Dijkstra implementado? Ou um outro algoritmo qualquer que calcule o menor caminho entre dois nós?[/quote]

puts cara, mas tu quer assim?! na lata?! implementado?! sem nem tentar fazer?!? pow, não acho muito legal eu simplesmente te dar… ainda mais dijkstra que é relativamente facil de achar no google heheh
mas tah se vc procurasse por simplesmente dijkstra aqui no forum, ia aparecer esse topico:
http://www.portaljava.com/home/modules.php?name=Forums&file=viewtopic&t=38257&highlight=dijsktra

o cara quer o maior caminho entre dois nós, uma variação de dijsktra, mas no quarto post dele, logo o primeiro código que ele posta é um dijkstra implementadinho e funcionando… é só ler o tópico e pegar la…

:wink: