2

Olá, estou começando ver grafos agora, estou tentando criar um programa onde o usuário entra com uma matriz de adjacência e o programa calcula o menor caminho possível do nó inicial até o final e que todas as arestas tenham o mesmo peso, mas não consegui achar uma forma para o programa saber que chegou até o ultimo nó, assim compararei com a variável auxiliar para saber qual o menor caminho

Fiz isto até agora:

static int tCaminho = 100, tAux = 0;
static int[][] ma = new int[8][8];
static Scanner scan = new Scanner(System.in);

public static void main(String[] args) {
    // TODO Auto-generated method stub

    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            ma[i][j] = scan.nextInt();
        }
    }

    caminho(0 , 0);
    System.out.println(tCaminho);
}

public static void caminho(int c, int cc){
    for(int j = cc; j < 8; ++j){
        if(ma[c][j] == 1){
            ++tAux;
            caminho(c+1, 0);
        }

        if(j == 7){
            if(tAux < tCaminho){
                tCaminho = tAux;
            }
            tAux = 0;
        }
    }
}

Alguém poderia ajudar (se estiver fazendo muita merda falem, estou estudando por conta própria)

1
  • Bem vindo ao Stack Overflow pt =). Espero que goste do site e da comunidade! Commented 10/08/2016 às 17:15

1 Resposta 1

2

Encontrar o menor caminho em um grafo é um pouco mais complexo que isso.

No seu caso onde todas as arestas tem o mesmo peso é possível utilizar uma busca em largura. O código a seguir é um exemplo de utilização da busca em largura para achar o menor caminho até todos os vértices.

public static int[] buscaLateral(int inicio, int[][] ma, int tam){
    int[] distancias = new int[tam];
    Queue<Integer> fila = new LinkedList<Integer>();

    // Inicializando a menor distância de todos os vértices ao inicial como -1
    for(int i=0; i<8; i++)
        distancias[i]=-1;

    // A distância do vértice inicial a ele mesmo é zero
    distancias[inicio] = 0;
    fila.add(inicio);

    // Executando a busca lateral
    while(!fila.isEmpty()){
        int atual = fila.remove();
        for(int i = 0; i < 8; i++)
            if(ma(atual, i, ma) == 1 && distancias[i] == -1){
                distancias[i] = distancias[atual] + 1;
                fila.add(i);
            }
    }
    return distancias;
}

Veja o código completo no Ideone.

A função ma foi feita apenas para acessar a matriz de adjacências do mesmo lado (pois geralmente ela é simétrica, caso não seja tire o if da função):

public static int ma(int i, int j, int[][] ma){
    if(i < j)
        return ma[i][j];
    else
        return ma[j][i];
}

Aqui está uma imagem que explica bem como ocorre a busca em largura:

Busca em largura

O algoritmo começa no nó inicial com valor 1. Este nó adiciona todos os seus vizinhos na fila e coloca valor 2 em todos. O próximo nó da fila adiciona todos os seus vizinhos que ainda não tem valor na fila e coloca os seus valores como 3. O algoritmo continua até acabarem todos os nós na fila. Os últimos nós não adicionam ninguém na fila, já que todos os seus vizinhos já terão valor. Por isso em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia terminando o algoritmo.

Repare que o algoritmo proposto só tem a diferença que o primeiro nó recebe valor zero e assim o valor de cada nó já é a menor distância ao primeiro nó. Esse algoritmo só funciona pois todas as distâncias são iguais. Caso as distâncias entre os nós não sejam todas iguais deve ser usada uma variação da busca em largura que se chama algoritmo de Dijkstra.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .