693833_Estudo Dirigido iV

Prévia do material em texto

Estudo Dirigido IV 
 
1)Geralmente, os sites que permitem determinar a menor rota entre dois pontos em uma 
cidade não levam em consideração o seguinte problema: o motorista nem sempre deseja 
encontrar exatamente o menor caminho, mas sim um caminho que seja, além de curto, 
fácil de seguir. Por exemplo, considere as duas opções abaixo. 
 
Apesar de maior, o primeiro caminho é mais fácil de seguir do que o segundo. 
Mostre como transformar este problema em um problema em grafos, de modo que o 
resultado seja um caminho curto e fácil de seguir. Para isso, você deverá, a partir do 
problema: 
(a) Definir o que são os vértices do grafo que deve ser montado para resolver este 
problema; 
(b) Definir em que situação dois vértices deste grafo são adjacentes, isto é, quando há 
arestas entre dois vértices deste grafo; defina também se há custo associado às arestas; 
(c) Enunciar o problema apresentado como um problema em grafos; 
(d) Citar o algoritmo que resolva da forma mais eficiente o problema apresentado. 
 
2) 
 
 
 
 
 
a)Para o grafo acima, mostre a sequência de vértices da busca em amplitude, partindo de 
D. 
b)Mostre a sequência de vértices da busca em profundidade, partindo de J 
c)Considerando que todas arestas têm peso 1, encontre o menor caminho entre E e K 
usando Djikstra.