Aula 10 - Grafos III: Menor Caminho

1 Flares Facebook 1 1 Flares ×

Aula por Lucca Siaudzionis

"O cientista Succa Liaudzionis decidiu tirar férias na Europa. Enquanto ele estava em seu descanso, o cientista Sictor Vales fez uma descoberta impressionante no quartel-general do Núcleo Organizado de Informática e Computação (NOIC). Agora, Succa precisa voltar imediatamente para o quartel do Noic para poder avaliar a descoberta. Succa foi para o aeroporto, mas a quantidade de voos disponíveis é muito grande (repare que alguns podem ter conexões e todos existem nos dois sentidos) e ele precisa saber qual o menor tempo para que possa voltar para a base."

Vamos montar o grafo que é importante para a vida do Succa.

Vértices: Cada uma das cidades disponíveis que possuem voos.

Arestas: Cada um dos voos. Aqui,  peso de cada aresta é o tempo de duração de voo.

Queremos então achar o menor caminho da cidade de onde Succa está para a cidade onde o Noic está.

Vamos comentar dois algoritmos muito conhecidos nesta aula: Algoritmo de Dijkstra Algoritmo de Floyd-Warshall.

Algoritmo de Dijkstra

Este algoritmo recebe um vértice principal S para ser a fonte do grafo e retorna o menor caminho de todos os vértices do grafo para S. Abordaremos, para este algoritmo, a solução em O(N^2), onde N é o número de vértices. Há, também, uma solução O(M \ lg N), que é muito mais rápida para grafos esparsos, mas não abordaremos nesta aula.

O Algoritmo consiste em:

  • Definir a distância como \infty para todos os vértices e como 0 para o vértice S.
  • Em cada passo, encontrar o vértice u, que ainda não foi processado, que possua a menor das distâncias. Este vértices agora foi fixado como já tendo a menor distância de S para ele.
  • Ver para cada vértice v, vizinho de u, se é melhor manter a distância atual de v ou atualizar fazendo o caminho S \rightarrow u e depois u \rightarrow v. Repare que o caminho S \rightarrow u já foi fixado e possivelmente tem conexões no meio.

Vamos dar uma olhada no que seria o pseudo-código desse algoritmo:

Olhe o seguinte grafo e sua correspondente matriz de adjacência.

Slice 1 V_1 V_2 V_3 V_4 V_5 V_6 V_7
V_1 \infty 3 \infty \infty \infty \infty 1
V_2 3 \infty 4 7 \infty \infty \infty
V_3 \infty 4 \infty 1 \infty \infty 9
V_4 \infty 7 1 \infty 8 \infty 4
V_5 \infty \infty \infty 8 \infty \infty \infty
V_6 \infty \infty \infty \infty \infty \infty \infty
V_7 1 \infty 9 4 \infty \infty \infty

Vamos simular o Dijkstra fazendo S = 1.

Primeiro, inicializamos as distâncias:

Slice 2g Distância
1 0
2 3
3 \infty
4 \infty
5 \infty
6 \infty
7 1

O vértice de menor distância é o 7. Então, selecionamos ele e atualizamos as distâncias dos vértices 3 e 4, que são seus vizinhos.

 

Slice 3 Distância
1 0
2 3
3 10
4 5
5 \infty
6 \infty
7 1

O novo vértice de menor distância é o 2. Selecionamos então ele e só alteramos a distância do vértice 3 (pois não compensa mudar o 4).

Slice 4 Distância
1 0
2 3
3 7
4 5
5 \infty
6 \infty
7 1

O novo vértice mais próximo é o vértice 4. Com ele, podemos atualizar a distância do vértice 5 e do vértice 3.

Slice 5 Distância
1 0
2 3
3 6
4 5
5 13
6 \infty
7 1

O novo vértice mais próximo é o 3, mas não conseguimos mudar nenhuma distância.

Slice 6 Distância
1 0
2 3
3 6
4 5
5 13
6 \infty
7 1

O novo vértice mais próximo é o 5, mas também não atualizamos nenhuma distância.

Slice 7 Distância
1 0
2 3
3 6
4 5
5 13
6 \infty
7 1

Repare que não iremos acessar o 6, apesar de ele ainda não ter sido acessado, por sua distância ser \infty. Vemos que calculamos a menor distância de 1 para todos os outro vértices. O fato de a distância de 1 ao 6 aparecer como sendo \infty significa que não existe caminho do vértice 1 ao vértice 6, o que pode ser facilmente observado como sendo verdade.

Vamos fazer o código, em C++, para o problema da Viagem de Succa. Vamos supor neste problema que o número de cidades é N \leq 1000 e que o a duração de cada viagem não passa de 1000 minutos.

 

Algoritmo de Floyd-Warshall

O Algoritmo de Floyd-Warshall, quando executado, retorna a menor distância entre todos os pares de vértices possíveis. Seu tempo de execução é O(N^3) e precisa de N^2 de memória. Note que, se quisermos a menor distância para todos os pares de vértices, podemos simplesmente executar o Algoritmo de Dijkstra N vezes (uma para cada vértice) e obteremos o mesmo resultado, no mesmo tempo e mesmo uso de memória. A diferença essencial, então, é que o código do Algoritmo de Floyd-Warshall é extremamente simples.

Olhe o pseudo-código do Algoritmo de Floyd-Warshall:

Como eu disse, bem simples o código.

Vamos então resolver o problema da Viagem de Succa usando o algoritmo de Floyd-Warshall (para poder o tempo ser suficiente, vamos reduzir N para N \leq 1000). Vamos aproveitar e dificultar um pouco problema. Succa irá fazer Q perguntas no formato "Qual o menor tempo de viagem da cidade S até a cidade E?". 

 

Esses dois algoritmos são muito conhecidos e é essencial saber usar corretamente os dois. Se o seu problema puder ser resolvido por Floyd-Warshall (não tiver problema com o tempo), é o mais sensato a se fazer devido a facilidade de implementar e debugar o algoritmo.

Algumas últimas observações:

i) No caso de todas as arestas terem peso igual a 1, pode-se, em vez de fazer o Algoritmo de Dijkstra, simplesmente fazer uma BFS no vértice desejado.

ii) os algoritmos não funcionam no caso de existir arestas com peso negativo.

Tente, agora, resolver os problemas abaixo para colocar em prática seus conhecimentos. Não deixe de tentar resolver também com Dijkstra os problemas que você resolver inicialmente com Floyd-Warshall, para poder melhorar seu treinamento. Caso tenha dificuldade em algum problema ou alguma dúvida sobre a teoria apresentada, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida!

Problema 1 - Caminho das Pontes

Problema 2 - Reunião

Problema 3 - Lanche na Empresa

Problema 4 - Desrugenstein

Problema 5 - Países em Guerra

Problema 6 - Empresa de Telecom

Problema 7 - Easy Dijkstra


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

1 Flares Facebook 1 1 Flares ×
1 Flares Facebook 1 1 Flares ×
%d bloggers like this: