Algoritmo Caminho Mais Proximo

Programação Java
#1

Ola pessoal

Estou com um problema de logica aqui para resolver ,
é o Seguinte :
Tenho 6 Cidades ,
a Distanco entre elas,
e Precisa percorre todas elas pelo menor caminho sem passar pela mesma cidade 2 x
e por fim chegar de volta a cidade inicial .

a Imagem mostra como seria partindo da cidade 6 :

o Caminho seria
6-1-3-4-5-2-6

Pois bem eu ja resolvi quase tudo falta so ele testar se ja passou pela cidade X e nao pegar a mesma 2 vezes , passei maior tempo tentando e nada .
alguem me ajude pls abaixo o Codigo Fonte :

[code]// Funcao que Seleciona a cidade com menor distancia
public class Teste
{
public static int pegaMenor(int distancias[])
{
int j=9;
int d=1;
for (int i=1; i<7; i++){
if(distancias[i]<j && distancias[i]!=0){
j=distancias[i];
d=i;
}
}
return(d);
}

// funçao que cria a Lista de cidades possiveis para cada Cidade
public static int[] listaCidades(int a){
int [][] x = new int [7][7];
int [] k = new int [7];
x[1][1] = 0;
x[2][2] = 0;
x[3][3] = 0;
x[4][4] = 0;
x[5][5] = 0;
x[6][6] = 0;
x[1][2] = 2;
x[1][3] = 1;
x[1][4] = 4;
x[1][5] = 9;
x[1][6] = 1;
x[2][1] = 2;
x[2][3] = 5;
x[2][4] = 9;
x[2][5] = 7;
x[2][6] = 2;
x[3][1] = 1;
x[3][2] = 5;
x[3][4] = 3;
x[3][5] = 8;
x[3][6] = 6;
x[4][1] = 4;
x[4][2] = 9;
x[4][3] = 3;
x[4][5] = 2;
x[4][6] = 6;
x[5][1] = 9;
x[5][2] = 7;
x[5][3] = 8;
x[5][4] = 2;
x[5][6] = 2;
x[6][1] = 1;
x[6][2] = 2;
x[6][3] = 6;
x[6][4] = 6;
x[6][5] = 2;
//cria e preenche vetor distancias
for (int i=1; i<7; i++){
k[i]=x[a][i];
}

  return(k);	  
}
   	  
   

							
public static void main(String[] args)
	{   
		
		
	 int cidadeInicial=6;
	 int proximaCidade=0;
	
	 int [] distancias = new int [7];
	 int [] circuitoParcial =new int [7];
	
	// Adiciona a Primeira Cidade ao Circuito
	  circuitoParcial[1]=cidadeInicial;
	 
	  distancias=listaCidades(cidadeInicial);
	  
	 // Laço Principal
	 for(int i=2;i<7;i++)  {
	 	
	 	// pega a proxima cidade mais perto
	 	proximaCidade= pegaMenor(distancias);
	 	
	 	// imprime a proxima cidade na tela 
	 	System.out.println(proximaCidade+" proximaCidade:" );
	 	
	 	// Atualiza o vetor distancias
		 distancias=listaCidades(proximaCidade);
	 
	 
	 	 	
	 	// inclui a cidade vizitada no circuito 
		 circuitoParcial[i]=proximaCidade;
	 	
	 }		 	
  		   	
	 // no final imprime o caminho percorrido 
     System.out.println("caminho Percorrido : " ); 
     for(int y=1;y<7;y++)  {
	 	 System.out.println( circuitoParcial[y] ); 
	 	 }
	  	
	 //System.out.println(b);	
	
	}

}[/code]

Por favor me ajudem , é meu primeiro programa em Java .

#2

Bom existem varias maneiras de resolver o seu problema, a primeira que eu pensei foi em criar um vetor booleano com o tamanho das cidades contendo false se ela ainda nao foi visitada e true se ela ja foi, o codigo ficaria assim :

public class Teste
{
public static int pegaMenor(int distancias[], boolean[] visitadas)
    {
        int j=Integer.MAX_VALUE;
        int d=1;
            for (int i=0; i<6; i++){
                if(distancias[i]<j && distancias[i]!=0 && !visitadas[i]){
                    j=distancias[i];
                    d=i;
                }
            }
        return(d);
    }



// funçao que cria a Lista de cidades possiveis para cada Cidade
public static int[] listaCidades(int a){
        int [][] x = new int [6][6];
        int [] k = new int [6];
            x[0][0] = 0;
            x[1][1] = 0;
            x[2][2] = 0;
            x[3][3] = 0;
            x[4][4] = 0;
            x[5][5] = 0;
            x[0][1] = 2;
            x[0][2] = 1;
            x[0][3] = 4;
            x[0][4] = 9;
            x[0][5] = 1;
            x[1][0] = 2;
            x[1][2] = 5;
            x[1][3] = 9;
            x[1][4] = 7;
            x[1][5] = 2;
            x[2][0] = 1;
            x[2][1] = 5;
            x[2][3] = 3;
            x[2][4] = 8;
            x[2][5] = 6;
            x[3][0] = 4;
            x[3][1] = 9;
            x[3][2] = 3;
            x[3][4] = 2;
            x[3][5] = 6;
            x[4][0] = 9;
            x[4][1] = 7;
            x[4][2] = 8;
            x[4][3] = 2;
            x[4][5] = 2;
            x[5][0] = 1;
            x[5][1] = 2;
            x[5][2] = 6;
            x[5][3] = 6;
            x[5][4] = 2;
//cria e preenche vetor distancias
             for (int i=0; i<6; i++){
                k[i]=x[a][i];
             }

      return(k);
    }




    public static void main(String[] args)
        {


         int cidadeInicial=5;
         int proximaCidade=0;

         int [] distancias = new int [6];
         int [] circuitoParcial =new int [6];
         boolean [] visitadas = new boolean[6];

        // Adiciona a Primeira Cidade ao Circuito
          circuitoParcial[0]=cidadeInicial;
          visitadas[cidadeInicial] = true;

          distancias=listaCidades(cidadeInicial);

         // Laço Principal
         for(int i=1;i<6;i++)  {

            // pega a proxima cidade mais perto
            proximaCidade= pegaMenor(distancias,visitadas);
            visitadas[proximaCidade] = true;

            // imprime a proxima cidade na tela
            System.out.println(proximaCidade+" proximaCidade:" );

            // Atualiza o vetor distancias
             distancias=listaCidades(proximaCidade);



            // inclui a cidade vizitada no circuito
             circuitoParcial[i]=proximaCidade;

         }

         // no final imprime o caminho percorrido
         System.out.println("caminho Percorrido : " );
         for(int y=0;y<6;y++)  {
             System.out.println( circuitoParcial[y]+1 );
             }

         //System.out.println(b);

        }

Ahh outra coisa eu notei que você aloca 7 posicoes no vetor/matriz porem só utiliza 6 no java o vetores começam na posição 0, modifiquei isso abraços!.

#3

Bocchi

Muito obrigado cara tua ajuda foi nota 1000
abraços vlw !

#4