Aula 10 - Grafos III: Menor Caminho

Aula por Lucca Siaudzionis

Com edições por Lúcio Cardoso

"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 e 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.

		$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:

	Nó	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.

 

	Nó	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$).

	Nó	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$.

	Nó	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.

	Nó	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.

	Nó	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.

Note que a complexidade do algoritmo descrito acima é $O(N?2)$, pois o loop principal será executado $N$ vezes (enquanto houver um vértice que não foi processado) e, nesse loop, encontramos o vértice com menor distância de $S$ em &&N&& operações. No entanto, é possível otimizar o algoritmo utilizando uma estrutura de dados do C++ chamada priority queue (veja esta aula para saber mais), que é uma fila capaz de manter seus elementos ordenados de maneira crescente em $O(logN)$ para cada operação.

Assim, podemos usar uma priority queue que guarda pares da forma $(d, v)$, onde &&d&& é a distância do vértice $v$ para $S$, organizando os pares de maneira crescente em relação a $d$. De tal forma, o vértice com menor distância de $S$ estará no topo da fila, e as operações de inserção e remoção serão feitas em $O(logN)$.

A implementação é, então, bastante parecida com a do algoritmo anterior; a principal diferença, além da fila de prioridade, será que vamos utilizar uma lista de adjacência, ao contrário da matriz, uma vez que percorrer a matriz $NxN$ tornaria nosso algoritmo quadrático (complexidade $O(N?2)$). Segue abaixo o código em C++:

https://gist.github.com/luciocf/75ea65b3f898767a4f6078db4ada09e9

Perceba que a complexidade do algoritmo é , já que para cada aresta partindo do vértice sendo processado no momento, faremos uma operação na priority queue em .

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.