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
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…
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:
- –> 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…
