Problemas com grafos

Programação Java
#1

Bom dia pessoal.

Estou com o seguinte problema. Eu e meu grupo da faculdade fizemos um programa utilizando grafos, que mostra rotas cadastradas.
Acontece que em uma instância do programa, ele está retornando uma distância que não existe, quando deveria retornar que não existe linha direta entre as cidades consultadas.
Explicitando mais o problema, quando, no menu principal, se escolhe “Verifica linha direta entre as cidades”, e na cidade de origem se digita uma cidade que existe no grafo, e na cidade de destino uma que não existe, ele retorna que a distância é 150 km.
Ex.: cid. origem = uberlandia
cid. destino = sao paulo

Vou publicar o código abaixo, na esperança que alguém possa me ajudar.

[code]//Declara e permite o uso da classe JOptionPane
import javax.swing.JOptionPane;

public class Rotas
{
public static void main (String args[])
{
//variáveis utilizadas na execução
int no, naoexiste, i, j, matriz[][], distancia[][], total, pos_origem, pos_destino;
String selOpcao, selOrigem, selDestino, cid_origem, cid_destino;

//vetor com cidades ORIGEM
String origem[] = {"ARAXA", "UBERABA", "MONTE CARMELO", "ITUMBIARA", "UBERLANDIA", "BRASILIA", "GOIANIA"};

//vetor com cidades DESTINO
String destino[] = {"ARAXA", "UBERABA", "MONTE CARMELO", "ITUMBIARA", "UBERLANDIA", "BRASILIA", "GOIANIA"};

//matriz que armazena as distâncias entre as cidades
matriz = new int[7][7];

//distância entre cidades (origem/destino)
distancia = new int[7][7];

//1ª linha
distancia[0][0] = 0;
distancia[0][1] = 150;
distancia[0][2] = 0;
distancia[0][3] = 0;
distancia[0][4] = 180;
distancia[0][5] = 0;
distancia[0][6] = 0;

//2ª linha
distancia[1][0] = 0;
distancia[1][1] = 0;
distancia[1][2] = 100;
distancia[1][3] = 0;
distancia[1][4] = 110;
distancia[1][5] = 0;
distancia[1][6] = 0;

//3ª linha
distancia[2][0] = 0;
distancia[2][1] = 100;
distancia[2][2] = 0;
distancia[2][3] = 0;
distancia[2][4] = 0;
distancia[2][5] = 0;
distancia[2][6] = 200;

//4ª linha
distancia[3][0] = 0;
distancia[3][1] = 0;
distancia[3][2] = 0;
distancia[3][3] = 0;
distancia[3][4] = 120;
distancia[3][5] = 0;
distancia[3][6] = 0;

//5ª linha
distancia[4][0] = 150;
distancia[4][1] = 0;
distancia[4][2] = 0;
distancia[4][3] = 0;
distancia[4][4] = 0;
distancia[4][5] = 350;
distancia[4][6] = 0;

//6ª linha
distancia[5][0] = 0;
distancia[5][1] = 0;
distancia[5][2] = 0;
distancia[5][3] = 0;
distancia[5][4] = 350;
distancia[5][5] = 0;
distancia[5][6] = 170;

//7ª linha
distancia[6][0] = 0;
distancia[6][1] = 0;
distancia[6][2] = 200;
distancia[6][3] = 230;
distancia[6][4] = 0;
distancia[6][5] = 170;
distancia[6][6] = 0;

for(i=0; i < 7; i++)
{
  for(j=0; j < 7; j++)
  {
    matriz[i][j] = distancia[i][j];
  }
}
    //menu de opções das tarefas a serem executadas
    Object[] listaOpcoes = {"Verifica o nó", "Quantidade de linhas de ônibus", "Verifica linha direta entre cidades", "Verifica distância total entre cidades"};
    selOpcao = (String) JOptionPane.showInputDialog(null, //janela pai
    "Selecione a opção desejada:", //Mensagem
    "Projeto PIH - Menu de Opções", //Titulo Janela
    JOptionPane.INFORMATION_MESSAGE, //Tipo da mensagem mostrada. Altera o desenho da tela e o ícone Padrão
    null, //Icone, neste caso será utilizado o ícone padrão
    listaOpcoes, //Vetor de objetos com as possíveis opções
    listaOpcoes[0]); //Valor inicial selecionado
    
    //Caso tenha selecionado CANCEL
    if (selOpcao == null)
    {
        JOptionPane.showMessageDialog(null, //janela Pai
                "Nenhuma opção selecionada! Cancelando...",  //Mensagem
                "Projeto PIH", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        return;
    }

    //se selecionou opção 1 no menu de opções
    if (selOpcao.equals(listaOpcoes[0]))
    { 
      System.out.println("Opção selecionada: "+  selOpcao);
     
     //monta menu de opções com nome das cidades
     Object[] listaCidades = {"ARAXA", "UBERABA", "MONTE CARMELO", "ITUMBIARA", "UBERLANDIA", "BRASILIA", "GOIANIA"};
     selOpcao = (String) JOptionPane.showInputDialog(null, //janela pai
     "Selecione a CIDADE desejada:", //Mensagem
     "Projeto PIH - Verifica o nó", //Titulo Janela
     JOptionPane.INFORMATION_MESSAGE, //Tipo da mensagem mostrada. Altera o desenho da tela e o ícone Padrão
     null, //Icone, neste caso será utilizado o ícone padrão
     listaCidades, //Vetor de objetos com as possíveis opções
     listaCidades[0]); //Valor inicial selecionado
    
    //Caso tenha selecionado CANCEL
    if (selOpcao == null)
    {
        JOptionPane.showMessageDialog(null, //janela Pai
                "Nenhuma opção selecionada! Cancelando...",  //Mensagem
                "Projeto PIH", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        return;
    }
       
       //variável que armazena a posição no grafo
       no = 0;
       
       //contador de cidades, caso não conste no grafo
       naoexiste = 0;
       
       //busca a cidade selecionada na matriz e 
       //verifica se a distância é diferente de 0
       for(i=0; i < 7; i++)
       {
         for(j=0; j < 7; j++)
         {
           if(origem[i].equals(selOpcao))
           {
             if(matriz[i][j] != 0)
             {
               no = i+1;
             }
           }
           else
           {
             naoexiste++;
           }
         }
       }
       
       //se percorreu toda a matriz e não encontrou
       if(naoexiste == 49)
       {
         JOptionPane.showMessageDialog(null, //janela Pai
                "Cidade " + selOpcao + " não cadastrada em nosso sistema!",  //Mensagem
                "Projeto PIH - Verifica o nó", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
         
         System.out.println("===> Clique em F2 para reinicializar <===");
         
         return;
       }
       else
       {
         //senão imprime a posição no grafo
         JOptionPane.showMessageDialog(null, //janela Pai
                "Pertence ao nó " + no + " do grafo.",  //Mensagem
                "Projeto PIH - Verifica o nó", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
         return;
       }
       
    }
    //se selecionou a opção 2 no menu de opções
    else if (selOpcao.equals(listaOpcoes[1]))
    {
      System.out.println("Opcao Selecionada: "+  selOpcao);
      
      //solicita a cidade para verificação das linhas de ônibus
      selOpcao =  JOptionPane.showInputDialog(null, //Janela origem - null console
                 "Informe a cidade (sem acentos ou caracteres especiais):", //Mensagem
                 "Projeto PIH - Quantidade de linhas de ônibus",//Titulo
                  JOptionPane.PLAIN_MESSAGE);//Tipo mensagem mostrada
      
      //retira espaços em branco e converte para maiúsculo, a cidade digitada
      selOpcao = selOpcao.trim();
      selOpcao = selOpcao.toUpperCase();
      
      //quantidade de linhas encontradas
      total = 0;
      
      //contador de cidades, caso não conste no grafo
      naoexiste = 0;
      
      //busca a cidade informada na matriz e 
      //verifica se a distância é diferente de 0
      for(i=0; i < 7; i++)
      {
        for(j=0; j < 7; j++)
        {
          if(origem[i].equals(selOpcao))
          {
            if(matriz[i][j] != 0)
            {
              total++;
              //System.out.println("Distância entre " + origem[i] + " e " + destino[j] + " => " + matriz[i][j]);
            }
          }
          else
          {
            naoexiste++;
          }
        }
      }
      
      //caso não encontre a cidade informada na matriz
      if(naoexiste == 49)
      {
        JOptionPane.showMessageDialog(null, //janela Pai
                "Cidade " + selOpcao + " não cadastrada em nosso sistema!",  //Mensagem
                "Projeto PIH - Quantidade de linhas de ônibus", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        
        System.out.println("===> Clique em F2 para reinicializar <===");
        
         return;
      }
      else
      {
        JOptionPane.showMessageDialog(null, //janela Pai
                "Existem " + total + " rota(s) para " + selOpcao,  //Mensagem
                "Projeto PIH - Quantidade de linhas de ônibus", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        System.out.println("===> Clique em F2 para reinicializar <===");
         return;
      }
      
    }
    //se selecionou a opção 3 no menu de opções
    else if (selOpcao.equals(listaOpcoes[2]))
    {
      System.out.println("Opção selecionada: "+  selOpcao);
      
      //solicita cidade ORIGEM
      selOrigem =  JOptionPane.showInputDialog(null, //Janela origem - null console
                   "Informe a cidade de ORIGEM (sem acentos ou caracteres especiais):", //Mensagem
                   "Projeto PIH - Verifica linha direta entre cidades",//Titulo
                    JOptionPane.PLAIN_MESSAGE);//Tipo mensagem mostrada
      
      cid_origem = selOrigem.trim();
      cid_origem = cid_origem.toUpperCase();
      
      //solicita cidade DESTINO
      selDestino =  JOptionPane.showInputDialog(null, //Janela origem - null console
                    "Informe a cidade de DESTINO (sem acentos ou caracteres especiais):", //Mensagem
                    "Projeto PIH - Verifica linha direta entre cidades",//Titulo
                    JOptionPane.PLAIN_MESSAGE);//Tipo mensagem mostrada

      //retira espaços em branco e converte para maiúsculo, a cidade digitada
      cid_destino = selDestino.trim();
      cid_destino = cid_destino.toUpperCase();
      
      //armazena a posição da cidade de origem na matriz
      pos_origem = 0;
      
      //armazena a posição da cidade de destino na matriz
      pos_destino = 0;
      
      //busca cidade origem e destino na matriz
      for(i=0; i < 7; i++)
      {
        if(cid_origem.equals(origem[i]))
        {
          pos_origem = i;
        }
        
        if(cid_destino.equals(destino[i]))
        {
          pos_destino = i;
        }
      }
      
      //se a distância é diferente de zero
      if(matriz[pos_origem][pos_destino] != 0)
      {
        JOptionPane.showMessageDialog(null, //janela Pai
        "Existe linha direta entre " + cid_origem + " e " + cid_destino + ".\n" 
        + "A distância é " + matriz[pos_origem][pos_destino] + " km.",  //Mensagem
        "Projeto PIH - Verifica linha direta entre cidades", //Titulo
        JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        
        System.out.println("===> Clique em F2 para reinicializar <===");
        
         return;
      }
      else
      {
        //se não encontrou a rota no grafo
        JOptionPane.showMessageDialog(null, //janela Pai
        "Não existe linha direta entre " + cid_origem + " e " + cid_destino,  //Mensagem
        "Projeto PIH - Verifica linha direta entre cidades", //Titulo
        JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        
         System.out.println("===> Clique em F2 para reinicializar <===");
        
         return;
      }
      
    }
    //se selecionou a opção 4 no menu de opções
    else if (selOpcao.equals(listaOpcoes[3]))
    {
      
      System.out.println("Opção selecionada: "+  selOpcao);
      
      //solicita cidade ORIGEM
      Object[] listaOrigem = {"ARAXA", "UBERABA", "MONTE CARMELO", "ITUMBIARA", "UBERLANDIA", "BRASILIA", "GOIANIA"};
      selOrigem = (String) JOptionPane.showInputDialog(null, //janela pai
      "Selecione a opção desejada:", //Mensagem
      "Projeto PIH - Verifica distância total entre cidades", //Titulo Janela
      JOptionPane.INFORMATION_MESSAGE, //Tipo da mensagem mostrada. Altera o desenho da tela e o ícone Padrão
      null, //Icone, neste caso será utilizado o ícone padrão
      listaOrigem, //Vetor de objetos com as possíveis opções
      listaOrigem[0]); //Valor inicial selecionado
    
              //Caso tenha selecionado CANCEL
              if (selOrigem == null)
              {
                JOptionPane.showMessageDialog(null, //janela Pai
                "Nenhuma ORIGEM selecionada! Cancelando...",  //Mensagem
                "Projeto PIH - Verifica distância total entre cidades", //Titulo
                JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
                return;
              }

      //solicita cidade DESTINO
      Object[] listaDestino = {"ARAXA", "UBERABA", "MONTE CARMELO", "ITUMBIARA", "UBERLANDIA", "BRASILIA", "GOIANIA"};
      selDestino = (String) JOptionPane.showInputDialog(null, //janela pai
      "Selecione o DESTINO desejado:", //Mensagem
      "Projeto PIH - Verifica distância total entre cidades", //Titulo Janela
      JOptionPane.INFORMATION_MESSAGE, //Tipo da mensagem mostrada. Altera o desenho da tela e o ícone Padrão
      null, //Icone, neste caso será utilizado o ícone padrão
      listaDestino, //Vetor de objetos com as possíveis opções
      listaDestino[0]); //Valor inicial selecionado
    
           //Caso tenha selecionado CANCEL
           if (selDestino == null)
           {
             JOptionPane.showMessageDialog(null, //janela Pai
             "Nenhum DESTINO selecionado! Cancelando...",  //Mensagem
             "Projeto PIH - Verifica distância total entre cidades", //Titulo
             JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
             return;
           }
      
      //armazena cidade origem selecionada
      cid_origem = selOrigem;
      
      //armazena cidade destino selecionada
      cid_destino = selDestino;
      
      //armazena posição da cidade origem na matriz
      pos_origem = 0;
      
      //armazena posição da cidade destino na matriz
      pos_destino = 0;
      
      //busca cidade origem e destino na matriz
      for(i=0; i < 7; i++)
      {
        if(cid_origem.equals(origem[i]))
        {
          pos_origem = i;
        }
        
        if(cid_destino.equals(destino[i]))
        {
          pos_destino = i;
        }
      }
      
      //se a distância entre a rota selecionada for diferente de 0
      if(matriz[pos_origem][pos_destino] != 0)
      {
        JOptionPane.showMessageDialog(null, //janela Pai
        "A distância entre " + cid_origem + " e " + cid_destino + " é " + matriz[pos_origem][pos_destino] + "km",  //Mensagem
        "Projeto PIH - Verifica distância total entre cidades", //Titulo
        JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        
        System.out.println("===> Clique em F2 para reinicializar <===");
        
         return;
      }
      else
      {
        JOptionPane.showMessageDialog(null, //janela Pai
        "Não existe rota entre " + cid_origem + " e " + cid_destino,  //Mensagem
        "Projeto PIH - Verifica distância total entre cidades", //Titulo
        JOptionPane.ERROR_MESSAGE); //Tipo da mensagem
        
         System.out.println("===> Clique em F2 para reinicializar <===");
        
         return;
      }
    }

}//fecha main
}//fecha class[/code]

Desde já agradeço a colaboração de vcs.
[ ]s
[size=“11”][color=“red”]* Editado: Lembre-se de utilizar BBCode em seus códigos - Ratinho[/color][/size] :joia:

#2

Olá pessoal.

Consegui descobrir onde está o problema. É o seguinte:

Toda vez que eu digitar, na opção 3 do menu principal, cidade de origem = uberlândia, e cidade destino qualquer uma que não exista, o programa retornará que a distância é 150 km.

Este erro acontece, pq a posição de uberlândia nos vetores é 4, e a de araxá é 0. Quando eu digito uma cidade que não existe, ele a armazena como 0 também. Ou seja, se eu pegar uberlandia como origem e uma cidade inexistente como destino, o programa interpretará como sendo a rota entre uberlandia e araxa.

Bom. Eu tentei ao final da condição para buscar a cidade de origem e destino e guardar nas variáveis “pos_origem” e “pos_destino”, incluir um senão, para que toda vez que não encontrar qualquer das cidades, atribuir 0 para as variáveis acima citadas.
Dessa forma, o programa vai procurar na matriz o valor atribuído à posição (0,0), que é 0, e retornará a mensagem que não existe a rota procurada, mas não deu certo.

Agora, pra qualquer rota, mesmo que exista, ele está retornando que não existe a rota procurada.

Gostaria de saber como que eu faço pra ele mostar as rotas genuínas, e mostrar que a rota não existe, quando acontecer um caso como o problema citado acima.

Parte do código onde está o problema:

//busca cidade origem e destino na matriz
for(i=0; i < 7; i++)
{
if(cid_origem.equals(origem[i]))
{
pos_origem = i;
}

        if(cid_destino.equals(destino[i]))
        {
          pos_destino = i;
        }
       }

Grato desde já.

#3