Fala galera!
tenho o seguinte problema:
um arquivo cidades.txt com o formato
CIDADE_A 0 3
CIDADE_B 3 7
CIDADE_C 3 0
CIDADE_D 6 6
CIDADE_E 6 0
CIDADE_F 9 3
onde a primeira coluna eh o nome da cidade sem espaço e as outras duas colunas as coordenadas X Y.
meu outro arquivo, chamado estradas.txt possui o seguinte formato:
CIDADE_A CIDADE_B
CIDADE_A CIDADE_C
CIDADE_B CIDADE_D
CIDADE_B CIDADE_E
CIDADE_C CIDADE_E
CIDADE_C CIDADE_D
CIDADE_D CIDADE_E
CIDADE_D CIDADE_F
CIDADE_E CIDADE_F
que mostra a ligação das cidades.
Eu preciso retornar um 3º arquivo com o resultado do menor caminho entra as cidades, por exemplo:
Cidade_D para:
Cidade_B => [Cidade_D, Cidade_B]: 3.1622776601683795
Cidade_F => [Cidade_D, Cidade_F]: 4.242640687119285
Cidade_E => [Cidade_D, Cidade_E]: 6.0
Cidade_C => [Cidade_D, Cidade_C]: 6.708203932499369
Cidade_A => [Cidade_D, Cidade_B, Cidade_A]: 8.16227766016838
tipo
mecher com entrada e saida de arquivos eu sei fazer numa boa…
o problema é mexer com algoritmo de menor caminho…
sei q existe o algoritmo de Dijkstra porém não sei como que vou fazer pra pegar as coordenadas do arquivo cidades.txt e fazer todo esse calculo :S
alguém pode me dar umas idéias??
vlww
Procure algoritmos para a solução do problema do caixeiro viajante. É esse seu mesmo caso.
ae kra
to enviando um zip com um ppt e 2 projetos do eclipse ensinando como usar dijkstra
qqr duvida manda ae
flww
[quote=Victor Maehira]Boa tarde!
Tenho uma sugestão:
Para usar Dijkstra você terá antes que calcular a distância (pesos) entre cada um dos pontos, dois a dois.
Para calcular a distãncia para cada dois pontos, você pode utilizar uma formulinha de geometrica analítica usando as coordenadas (http://www.brasilescola.com/matematica/definicao-geometria-analitica.htm)
Tendo as distâncias, rode o Dijkstra e boa sorte!!! rs
[/quote]
se eu fizer isso então, eu devo primeiro ver na linha oq é digito né?
pq se eu ler a linha toda com BufferedReader.ReadLine() ele nao vai ter como pegar os numeros e fazer o calculo né? ou vai?
ele vai ver tudo como uma string neh…
putz, impossivel fazer isso
:?
A minha idéia seria:
pegar a linha e botar em uma String,
depois quebrala com um split para pegar apenas o primeiro termo da linha assim:
String s=BufferedReader.ReadLine();
String nome=s.split(" ")[0] , x , y;
x=s.split(" ")[1];
y=s.split(" ")[2];
Pronto peguei o nome da cidade, posição x e y;
agora faz isso com ambas cidades e calcula.
poww eu não conhecia o split…
um colega da faculdade até havia me falado dele hj por coincidencia…
vou testar agora e ver se da certo…
maneiro!
vlw!
bom,
mesmo lendo a documentação não entendi direito como usa-lo…
essa parte de expressões regulares eu não vi ainda…
se alguém quiser se habilitar a explicar sucintamente eu agradeço! 
Aew
fiz assim e deu certinho…
try{
buffer = new BufferedReader(new FileReader("cidades.txt"));
buffer2 = new BufferedReader(new FileReader("estradas.txt"));
String linha = "";
String [] coord = null;
String Stringcidade = null;
float x;
float y;
while(eof == true){
linha = buffer.readLine();
if(linha == null){
eof = false;
}else{
coord = linha.split("\s");
Stringcidade = coord[0];
x = Float.parseFloat(coord[1]);
y = Float.parseFloat(coord[2]);
arrayCidades.add(new Cidades(Stringcidade,x,y));
}
}
}
Boa tarde!
Tenho uma sugestão:
Para usar Dijkstra você terá antes que calcular a distância (pesos) entre cada um dos pontos, dois a dois.
Para calcular a distãncia para cada dois pontos, você pode utilizar uma formulinha de geometrica analítica usando as coordenadas (http://www.brasilescola.com/matematica/definicao-geometria-analitica.htm)
Tendo as distâncias, rode o Dijkstra e boa sorte!!! rs
Oi Alexandre!
Tem várias formas de fazê-lo!
Uma idéia é:
Para cada linha no formato:
cadade x y
onde (x,y) são as coordenadas.
Você pode utilizar StringTokenizer para “quebrar” a String e pegar as coordenadas. Então, terá que dar parse para transformar X e Y em tipos numéricos para poder calcular.