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:

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