Menores caminhos

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

opa vlw cara!

[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
:?
:cry:

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! :smiley:

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.