MAC0338   Análise de Algoritmos

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.

Distâncias em um grafo

Esta página é um resumo do Capítulo 23, Seções 1 e 2, de CLR. Palavras-chave: distância, busca em largura.

Distâncias

O comprimento de um caminho é o número de arestas do caminho.  A distância de um vértice r a um vértice v é o comprimento de um caminho de comprimento mínimo que começa em r e termina em v. É claro que a distância de r a v pode não ser igual à distância de v a r. A distância de r a v é infinita se não existe caminho algum de r a v (ou seja, se v não estiver no território de r.) No presente caso, infinito = número de vértices do grafo.

(Convém insistir em dois pontos: 1. A distância de r a v é 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 r a k é k" equivale a duas afirmações:  (1) existe um caminho de r a v de comprimento é k;  (2) não existe caminho de r a v de comprimento menor que k.

PROBLEMA:  Dado um vértice r de um grafo, encontrar a distância de r a cada um dos demais vértices.

PROBLEMA':  Dado um vértice r de um grafo, encontrar um caminho de comprimento mínimo de r a cada um dos demais vértices.

Algoritmo das distâncias: rascunho

O algoritmo explora o grafo a partir de s. Todos os vértices são inicialmente NÃOVISTOs. À 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] := NÃOVISTO
      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] = NÃOVISTO 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.

Algoritmo das distâncias

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] := NÃOVISTO       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] = NÃOVISTO 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,

1. todo vértice ROTULADO está em Q e todo vértice em Q é ROTULADO;
2. para todo vértice v que seja ROTULADO ou EXAMINADO, o valor de d[v] é finito e igual à distância de s a v;
3. para todo vértice v que seja NÃOVISTO, temos d[v] = INFINITO;
4. não existe aresta (u,v), tal que u é EXAMINADO e v é NÃOVISTO.

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 é q₁,  o segundo é q₂,  etc.,  o último é q_r.  Digamos, ainda, que d[q₁] = k. Então, no início de cada iteração,

1. d[q₁]   <=   d[q₂]   <=   . . .   <=   d[q_r]   <=   k+1,
2. se x é EXAMINADO então d[x] <= k .

Detalhes de implementaçã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.

Exemplo

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.

A figura seguinte dá o estado dos vetores d (à esquerda) e Q (à direita) no início de cada iteração.  O caracter "-" indica INFINITO.

Eficiência do algoritmo

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

Exercícios

5. Mostre que no fim da execução algoritmo DISTÂNCIAS tem-se   d[v] <= d[u]+1   para toda aresta (u,v).  (Suponha que INFINITO+1 = INFINITO.)
   
   
6. Escreva uma versão do algoritmo das distâncias supondo que o grafo tem vértices 1, 2, . . . , n e é representado por sua matriz de adjacência A:  para cada par u,v de vértices, A[u,v]=1 se (u,v) é uma aresta e A[u,v]=0 em caso contrário. 
   
   

Caminhos mínimos

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 .