Skip to main content
3 de 3
adicionou 48 caracteres ao conteúdo
Sérgio Mucciaccia
  • 2,9mil
  • 1
  • 19
  • 31

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.

Sérgio Mucciaccia
  • 2,9mil
  • 1
  • 19
  • 31