Pelas caridades,
alguem tem o algoritmo de Dijkstra implementado? Ou um outro algoritmo qualquer que calcule o menor caminho entre dois nós?
Dijkstra (menor caminho)
A
8 Respostas
D
jah existe essa pergunta no forum… procura ae
H
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…
D
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…
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
A
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]
T
/*
* 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:
[email removido]
vlw!
L
Pelas caridades,alguem tem o algoritmo de Dijkstra implementado? Ou um outro algoritmo qualquer que calcule o menor caminho entre dois nós?
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…
Criado 5 de julho de 2005
Ultima resposta 11 de mai. de 2007
Respostas 8
Participantes 6