Início » Aulas » [ED1] Aula 65 – Grafos – Busca pelo Menor Caminho

[ED1] Aula 65 – Grafos – Busca pelo Menor Caminho

Olá a todos,

Na aula de hoje iremos ver como funciona a busca pelo menor caminho em grafos.
O menor caminho (ou caminho geodésico) entre dois vértices é o caminho que apresenta o menor comprimento dentre todos os possíveis caminhos que conectam esses vértices. No caso, o comprimento se refere ao número de arestas que conectam os dois vértices. Considerando um grafo ponderado, podemos também calcular o comprimento do caminho como sendo a soma dos pesos das arestas que compõem esse caminho.

Uma das maneiras de achar o menor caminho é utilizando o algoritmo de Dijkstra, como veremos nesta aula.

Exemplos de aplicações que usam esse tipo de busca incluem:
– achar o grau de separação entre duas pessoas em uma rede social;
– achar um trajeto em um mapa rodoviário;
– programar robôs explorar áreas;
– algoritmos de roteamento.

Até a próxima

Anúncios

3 Comentários

  1. Willian disse:

    Olá! Acompanho suas vídeo-aulas há algum tempo. Primeiramente gostaria de agradecer o conteúdo de altíssima qualidade disponibilizado no youtube e aqui no site.

    Estou estudando o algoritmo de menor caminho em grafos no momento, então implementei o código desta aula. Porém acho que possui algum erro pois a saída do algoritmo é diferente da calculada e esperada.

    Ficaria muito grato caso pudesse me ajudar a resolver esse problema.

    Abraço! 🙂

  2. Iso disse:

    Excelentes aulas, muito bem explicado! Parabéns! Seria perfeito se mostrasse como imprimir o grafo criado em uma matriz ou mostrar o menor caminho de um determinado vértice ao outro.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: