Skip to main content
adicionou 48 caracteres ao conteúdo
Fonte Link
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 distanciadistâ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 vizinhovizinhos que ainda não tem valor na fila e coloca o seu valoros 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 nósseus vizinhostemterão valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e aiterminando o algoritmo termina.

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.

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 distancia 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 ela é simétrica):

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 vizinho que ainda não tem valor na fila e coloca o seu valor 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 nóstem valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e ai o algoritmo termina.

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.

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 vizinhosterã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.

conteúdo editado
Fonte Link
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>();
    
    // InicialinzandoInicializando a menor distancia de todos os vértices ao inicial como -1
    for(int i=0; i<8; i++)
        distancias[i]=-1;
    
    // OA distanciadistâ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 ela é simétrica):

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 vizinho que ainda não tem valor na fila e coloca o seu valor 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 nós já tem valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e ai o algoritmo termina.

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.

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>();
    
    // Inicialinzando a menor distancia de todos os vértices ao inicial como -1
    for(int i=0; i<8; i++)
        distancias[i]=-1;
    
    // O distancia 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 ela é simétrica):

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 vizinho que ainda não tem valor na fila e coloca o seu valor 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 nós já tem valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e ai o algoritmo termina.

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.

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 distancia 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 ela é simétrica):

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 vizinho que ainda não tem valor na fila e coloca o seu valor 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 nós já tem valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e ai o algoritmo termina.

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.

Fonte Link
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>();
    
    // Inicialinzando a menor distancia de todos os vértices ao inicial como -1
    for(int i=0; i<8; i++)
        distancias[i]=-1;
    
    // O distancia 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 ela é simétrica):

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 vizinho que ainda não tem valor na fila e coloca o seu valor 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 nós já tem valor. Por isso que em determinado momento os nós acabam e a fila vai esvaziando até ficar completamente vazia e ai o algoritmo termina.

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.