Página preparada por Paulo
Feofiloff para a disciplina MAC 338 Análise de
Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/distancias.htm.
Esta página é um resumo do Capítulo 23, Seções 1 e 2, de CLR. Palavras-chave: distância, busca em largura.
O comprimento de um caminho é o número de arestas do caminho. A distância de um vértices s a um vértice t é o comprimento de um caminho de comprimento mínimo que começa em s e termina em t. É claro que a distância de s a t pode não ser igual à distância de t a s. A distância de s a t é infinita se não existe caminho algum de s a t (ou seja, se t não estiver no território de s.)
(Convém insistir em dois pontos: 1. A distância de s a t é um número. 2. Não faz sentido dizer "distância mínima": a distância já é mínima por definição.)
É importante ressaltar que a afirmação "a distância de s a t é k" equivale a duas afirmações: (1) existe um caminho de s a t cujo comprimento é k; (2) não existe caminho de s a t cujo comprimento seja menor que k.
PROBLEMA: Dado um vértice s de um grafo, encontrar a distância de s a cada um dos demais vértices.
O algoritmo explora o grafo a partir de s. Todos os vértices são inicialmente IGNORADOs. À medida que o algoritmo progride, um vértice pode se tornar ROTULADO e depois EXAMINADO. Um vértice se torna ROTULADO quando é atingido pela primeira vez e permanece ROTULADO enquanto seus vizinhos não tiverem sido todos explorados. Quando todos os vizinhos de um vértice já adquiriram o estado ROTULADO, o vértice se torna EXAMINADO.
O algoritmo supõe que os vértices do grafo são 1, 2, . . . , n.
RASCUNHO (n, Adj, s)
para u := 1 até n faça
estado[u] := IGNORADO
d[u] := INFINITO
estado[s] := ROTULADO
d[s] := 0
enquanto estado[u] = ROTULADO para algum u faça
para cada v em Adj[u] faça
se estado[v] = IGNORADO então
estado[v] := ROTULADO
d[v] := d[u]+1
estado[u] := EXAMINADO
devolva d
O algoritmo funciona corretamente? Não! (Dê um contra-exemplo!)
É preciso que os vértices de estado ROTULADO sejam examinados na mesma ordem em que foram encontrados. Para administrar esse ordem, vamos guardar os vértices de estado ROTULADO em uma fila.
Nosso algoritmo recebe um grafo, e um vértice s. O algoritmo devolve um vetor d: para cada vértice v, o número d[v] é a distância de s a v.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
DISTÂNCIAS (n, Adj, s)
para u := 1 até n faça
estado[u] := IGNORADO
d[u] := INFINITO
estado[s] := ROTULADO
d[s] := 0
Q := INICIALIZA-FILA(s)
enquanto Q não está vazia faça
u := PRIMEIRO-DA-FILA(Q)
para cada v em Adj[u] faça
se estado[v] = IGNORADO então
estado[v] := ROTULADO
d[v] := d[u]+1
INSIRA-NA-FILA(Q,v)
REMOVA-DA-FILA(Q)
estado[u] := EXAMINADO
devolva d
O paradigma desse algoritmo é conhecido como busca em largura. Esse mesmo paradigma é usado em muitos outros algoritmos sobre grafos.
Ao longo do algoritmo, Q é uma fila de vértices; essa fila é o segredo do funcionamento do algoritmo. O comando INICIALIZA-FILA(s) cria uma fila com um só elemento igual a s. O comando PRIMEIRO-DA-FILA(Q) devolve o primeiro elemento da fila Q mas não retira esse elemento da fila. O comando INSIRA-NA-FILA(Q,v) insere v no fim da fila Q. O comando REMOVA-DA-FILA(Q) remove o primeiro elemento.
O algoritmo funciona corretamente? Para responder esta pergunta é preciso entender a situação no início de cada iteração do processo iterativo que começa na linha 7. No início de cada iteração,
Portanto, quando a execução do algoritmo termina, o vetor d dá as distâncias corretas de s a cada um dos demais vértices.
Para mostrar que os quatro invariantes de fato valem no início de cada iteração é preciso fazer a seguinte observação auxiliar sobre a estrutura da fila Q. Digamos que o primeiro vértice de Q é q1, o segundo é q2, etc., o último é qr. Digamos, ainda, que d[q1] = k. Então, no início de cada iteração,
Como implementar a fila Q? A fila pode ser implementada, muito simplesmente, em um vetor Q[1..n]. Será preciso ter um índice i para marcar o início da fila e um índice f para marcar a primeira posição vaga na fila. A linha 6 do algoritmo consiste simplesmente em
i := 1
f := 2
Q[1] := s
A linha 7 do algoritmo consiste simplesmente em
enquanto i < f faça
A linha 8 do algoritmo consiste simplesmente em
u := Q[i]
A linha 13 consiste em
Q[f] := v
f := f+1
A linha 14 consiste em
i := i+1
A fila assim implementada jamais sofrerá "overflow", pois cada vértice do grafo entra na fila no máximo uma vez. Ademais, no início de cada iteração,
Q[1..i-1] contém todos os vértices EXAMINADOs e
Q[i..f-1] contém todos os vértices ROTULADO.
| 1 | i | f | n | ||||||||
| s | q1 | q2 | qr |
Eis um grafo com vértices s, v, x, y, w. A figura indica, para cada vértice u, a lista Adj[u] dos vértices adjacentes a u.
| s | x | ||
| v | z | ||
| x | w | y | |
| y | s | x | z |
| w | s | ||
| z | s | x |
A figura seguinte dá o estado dos vetores d (à esquerda) e Q (à direita) no início de cada iteração. O caracter "-" indica INFINITO.
| s | v | x | y | w | z | 1 | 2 | 3 | 4 | 5 | 6 | |
| 0 | - | - | - | - | - | s | ||||||
| 0 | - | 1 | - | - | - | s | x | |||||
| 0 | - | 1 | 2 | 2 | - | s | x | w | y | |||
| 0 | - | 1 | 2 | 2 | - | s | x | w | y | |||
| 0 | - | 1 | 2 | 2 | 3 | s | x | w | y | z | ||
| 0 | - | 1 | 2 | 2 | 3 | s | x | w | y | z |
Quanto tempo o algoritmo consome no pior caso? Vamos medir esse tempo em relação a dois parâmetros: o número n de vértices e o número m de arestas.
O tempo gasto com as operações de inicialização nas linhas 1 a 6 não passa de
O(n) .
É melhor não tentar estimar, em separado, o tempo gasto com cada execução do bloco de linhas 7-15. É melhor estimar o tempo total gasto com cada tipo de operação. (Imagine que o algoritmo cobra R$1 para executar cada operação e conte o total de dinheiro gasto no fim.)
Cada vértice entra na fila no máximo uma vez e sai da fila no máximo uma vez. Portanto, o tempo total dedicado às operações de manipulação da fila (linhas 6, 8, 13 e 14) é
O(n) .
A lista de adjacências de cada vértice é percorrida (linha 9) no máximo uma vez. A soma dos comprimentos de todas as listas de adjacências é igual ao número de arestas do grafo. Portanto, o tempo total gasto em todas as varreduras de listas de adjacência (linhas 9, 10, 11, 12) é
O(m) .
Conclusão final: o consumo de tempo de DISTÂNCIAS é
O(n+m) .
Agora que resolvemos o problema das distâncias em um grafo, podemos pedir mais informações:
PROBLEMA: Dados um vértice s de um grafo, encontrar um caminho de comprimento mínimo de s a cada um dos demais vértices.
Como essa multidão de caminhos pode ser representada? Resposta: Por meio de uma árvore de caminhos mínimos (ou árvore de busca em largura) representada por um vetor de predecessores.
É fácil modificar o algoritmo DISTÂNCIAS de tal modo que ele registre os predecessores dos vértices e portanto construa uma árvore de caminhos mínimos. Logo depois da linha 12, anote o predecessor u de v:
pred[v] := u .