[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

[ED1] Aula 64 – Grafos – Busca em Largura

Olá a todos,

Na aula de hoje iremos ver como funciona a busca em largura em grafos.
Nela, a busca parte de um vértice inicial e explora todos os vizinhos de um vértice. Em seguida, para cada vértice vizinho, ela repete esse processo, visitando os vértices ainda inexplorados.
Exemplos de aplicações que usam esse tipo de busca incluem:

- roteamento: encontrar um número mínimo de hops em uma rede. Os hops são os vértices intermediários no caminho correspondente à conexão;
– encontrar número mínimo de intermediários entre 2 pessoas.

Até a próxima aula.

Seguir

Obtenha todo post novo entregue na sua caixa de entrada.

Junte-se a 2.406 outros seguidores

%d blogueiros gostam disto: