Material complementar

Pessoal,

Recebi diversas mensagens sobre problemas de links quebrados na seção de material complementar.
Espero ter arrumado todos.

Nos próximos dias começaremos as aulas sobre árvores

Até lá

[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

Seguir

Obtenha todo post novo entregue na sua caixa de entrada.

Junte-se a 2.487 outros seguidores

%d blogueiros gostam disto: