Grafos 03 – Menor Caminho

Aula por Lúcio Cardoso

Imagine que temos um grafo com $$N$$ vértices e $$M$$ arestas, cada uma delas contendo um peso (um valor positivo arbitrário). Além disso, é dado um vértice $$S$$ qualquer do grafo. O problema do Menor Caminho consiste em calcular, para cada vértice $$V$$, a menor distância de $$S$$ para $$V$$, isto é, a menor soma possível de pesos de arestas que formem um caminho de $$S$$ para $$V$$.

Como um exemplo, se definirmos a origem $$S$$ como o vértice $$1$$ do grafo acima, teremos que:

  • O menor caminho para o vértice $$1$$ é $$0$$.
  • O menor caminho para o vértice $$2$$ é $$4$$.
  • O menor caminho para o vértice $$3$$ é $$7$$.
  • O menor caminho para o vértice $$4$$ é $$5$$.
  • O menor caminho para o vértice $$5$$ é $$1$$.

Nessa aula, serão abordados dois algoritmos bastante conhecidos para resolver o problema do Menor Caminho: O algoritmo de Dijkstra e o algoritmo de Floyd-Warshall.

Algoritmo de Dijkstra

O algoritmo de Dijkstra é usado para resolver o problema citado acima. Ele consiste das seguintes etapas:

  1. Inicialmente, marque todos os vértices do grafo como não visitados. Além disso, defina a distância atual para $$S$$ (origem) como $$0$$ e para todos os outros vértices como $$\infty$$.
  2. Encontre, dentre os vértices não visitados, aquele com menor distância atual. Chame-o de $$U$$ e marque-o como visitado. Assim, a distância atual de $$U$$ é, de fato, a sua menor distância para $$S$$ e $$U$$ não será visitado novamente.
  3. Para todo vizinho de $$V$$ de $$U$$, cheque se $$d_{at}(S, V) > d(S, U) + w(U, V)$$, onde $$d_{at}(S, V)$$ é a distância atual de $$V$$, $$d(S, U)$$ é o menor caminho de $$U$$ e $$w(U, V)$$ é o peso da aresta que liga $$U$$ e $$V$$. Se sim, atualize a distância atual de $$V$$ para $$d(S, u) + w(u, v)$$.
  4. Repita as etapas $$2$$ e $$3$$ até que todos os vértices do grafo estejam marcados.

Por que o Algoritmo de Dijkstra funciona?

Suponha que em um momento qualquer do algoritmo, o vértice $$V$$ é o vértice não marcado mais próximo de $$S$$, ou seja, aquele cujo menor caminho para $$S$$ é mínimo. Perceba que o menor caminho de $$S$$ para $$V$$ é composto pelo menor caminho de $$S$$ para algum vértice $$U$$ seguido de uma aresta de $$U$$ para $$V$$. Como as arestas tem pesos positivos, o menor caminho de $$U$$ é certamente menor que o menor caminho de $$V$$. Logo, como $$V$$ é definido como o vértice não marcado de menor caminho mínimo, teremos que o vértice $$U$$ certamente já foi marcado. Porém, assim que $$U$$ for marcado, a etapa $$3$$ do algoritmo será realizada em seus vizinhos, e em particular, a distância atual de $$V$$ será atualizada para $$d(S, U) + w(U, V)$$, que é exatamente o menor caminho de $$V$$!

Queremos agora provar que o vértice escolhido na etapa $$2$$ é exatamente o vértice $$V$$. Suponha que o vértice não marcado de menor distância atual é um vértice $$W \neq V$$. Então, teremos que

$$d_{at}(S, W) < d_{at}(S, V)$$.

Como mostrado acima,

$$d_{at}(S, V) = d(S, V) \implies d_{at}(S, W) < d(S, V)$$.

Mas

$$d(S, W) \leq d_{at}(S, W)$$ (por definição) $$\implies d(S, W) < d(S, V)$$

uma contradição, já que $$V$$ foi definido como o vértice não marcado de menor caminho mínimo. Logo, $$V$$ será o vértice escolhido na etapa $$2$$ do algoritmo, e além disso, sua distância atual será igual à sua menor distância para $$S$$, o que conclui a prova.

Para implementar o algoritmo de Dijkstra, representaremos o nosso grafo como uma Lista de Adjacência. Além disso, vamos usar uma Fila de Prioridade que irá guardar pares da forma $$(d_{at}(v), v)$$, ou seja, a fila será ordenada de maneira crescente pela distância atual de cada vértice. Isso será de grande utilidade para realizarmos a etapa $$2$$ de maneira eficiente.

Confira o código abaixo:

Complexidade do algoritmo

Note que para cada vértice $$U$$, ao atualizarmos as distâncias dos seus vizinhos na etapa $$3$$, o número máximo de vértices que serão adicionados na fila é $$deg(U)$$, onde $$deg(U)$$ é o grau (quantidade de vizinhos) do vértice $$U$$. Portanto, a quantidade total máxima de vértices que serão adicionados na fila é igual a $$\sum_{i=1}^N {deg(i)} = 2\cdot M$$, já que, neste somatório, cada aresta do grafo será contada duas vezes.

Finalmente, como as operações da Fila de Prioridade possuem complexidade $$O(\log{}N)$$, a complexidade do algoritmo de Dijkstra será $$O(2 \cdot M \cdot \log{}N) = O(M \cdot \log{}N)$$.

Algoritmo de Floyd-Warshall

O algoritmo de Floyd-Warshall é utilizado para calcular a menor distância entre todos os pares de vértices do grafo, diferentemente do algoritmo de Dijkstra. A ideia do algoritmo consiste em perceber que todo menor caminho $$u \to v$$ com mais de 2 vértices pode ser decomposto em dois menores caminhos: $$u \to k$$ e $$k \to v$$, onde $$k$$ é um vértice intermediário no caminho $$u \to v$$.

Vamos definir $$d(u, v, k)$$ como a menor distância do vértice $$u$$ para o vértice $$v$$ considerando que o caminho $$u \to v$$ possui apenas vértices intermediários com índice menor ou igual a $$k$$. Assim, para cada par $$(u, v)$$ de vértices, teremos que

$$d(u, v, k)$$ = $$\begin{cases} w(u, v) & , \mbox{se k = 0} \\ min \big (d(u, v, k-1), d(u, k, k-1) + d(k, v, k-1) \big ) & , \mbox{caso contrario}\end{cases}$$

onde $$w(u, v)$$ é o peso da aresta $$(u \to v)$$. Se $$u = v$$, então $$d(u, v, 0) = 0$$, e se não existe uma aresta ligando $$u$$ e $$v$$, então definiremos $$d(u, v, 0)$$ como $$\infty$$. Perceba que $$d(u, v, N)$$ será exatamente igual ao menor caminho de $$u$$ para $$v$$, já que poderemos usar qualquer vértice como vértice intermediário.

A implementação do algoritmo de Floyd-Warshall é bastante simples. Confira o código abaixo:

Perceba que durante o código, não é necessário guardar $$d(u, v, k)$$ – podemos guardar apenas $$d(u, v)$$ representando a menor distância atual de $$u$$ para $$v$$, já que quando utilizamos o vértice $$k$$ como intermediário, $$d(u, v)$$ é exatamente igual a $$d(u, v, k)$$.

Complexidade do algoritmo

A complexidade do algoritmo de Floyd-Warshall é extremamente simples de se calcular. Para cada vértice intermediário $$k$$ de 1 a $$N$$, atualizaremos a distância de cada par de vértices $$(u,v)$$. Logo, a complexidade do algoritmo é $$O(N \cdot N^2) = O(N^3)$$.

Observação

Os algoritmos apresentados acima funcionam em grafos com arestas de pesos não-negativos e não funcionam caso alguma delas tenha peso negativo.

Problemas para Praticar

Tente resolver os problemas a seguir de variados níveis de dificuldade para fixar os conteúdos vistos e exercitar sua criatividade.