Distâncias em um digrafo

Esta página discute um algoritmo para o cálculo da distância entre dois vértices em um digrafo. O algoritmo é uma importante aplicação da busca em largura.

Esta página é inspirada nas seções 1 e 2 do capítulo 24 do CLRS.

Distância

O comprimento de um passeio em um digrafo é o número de arcos do passeio.  A distância de um vértice r a um vértice s é o comprimento de um passeio de comprimento mínimo que começa em r e termina em s(Todo passeio de comprimento mínimo é necessariamente um caminho.  Assim, a distância de r a s é o comprimento de um caminho de comprimento mínimo.) 

É claro que a distância de r a s pode ser diferente da distância de sr. A distância de r a s é infinita se não existe passeio algum de rs, ou seja, se s não estiver no território de r.  A afirmação a distância de r a s é d equivale a duas afirmações:  (1) existe um passeio de r a s cujo comprimento é d  e  (2) não existe passeio de r a s cujo comprimento seja menor que d.

Problema das distâncias:  Dado um vértice r de um digrafo, encontrar a distância de r a cada um dos demais vértices.

Poderíamos, igualmente bem, solicitar apenas as distâncias de r a cada vértice do território de r, já que todas as demais distâncias são infinitas.

Convém insistir em quatro pontos óbvios: 1. A distância de r a s é um número e não um passeio.  2. Não faz sentido dizer o comprimento mínimo de um passeio, uma vez que todo passeio tem um comprimento bem determinado que não é passível de minimização. 3. Não faz sentido dizer distância mínima, pois a distância já é mínima por definição. 4. Em virtude do caráter orientado dos passeios, convém não usar a expressão distância entre dois vértices.

Exercícios

  1. Sejam r e s dois vértices em um digrafo e seja P um passeio de comprimento mínimo dentre os que têm origem r e término s. Mostre que P é um caminho.

Algoritmo da distância

Para encontrar a distância de r a cada um dos demais vértices, basta fazer uma adaptação apropriada do algoritmo Busca-em-Largura.  O vetor cor daquele algoritmo será substituído por um vetor de distâncias dist:  para cada vértice v, o número dist[v] será a distância de r a v.  Os vértices brancos do algoritmo Busca-em-Largura corresponderão aos vértices v para os quais dist[v] vale ∞.  Não é preciso discutir a correspondência entre vértices cinza e valores de dist porque a fila torna os vértices cinza supérfluos, conforme exercício na página Território de um vértice.

O código abaixo supõe que os vértices do digrafo são  1, 2, … , n  e que os arcos são representados pelo vetor Adj[1..n] de listas de adjacência.

  Distâncias (n, Adj, r)
1o para u ← 1 até n faça
1oooo dist[u] ← ∞
1o dist[r] ← 0
1o FCria-Fila(r)
1o enquanto  F  não estiver vazia faça
1oooo uSai-da-Fila(F)
1oooo para cada v em Adj[u] faça
1ooooooo se dist[v] = ∞
1oooooooooo então  dist[v] ← dist[u]+1
10  oooooooooo então  Entra-na-Fila(v, F)
11  o devolva  dist[1..n]

O comando Cria-Fila(r) cria uma fila com um só elemento igual a r.  O comando Sai-da-Fila(F) retira o primeiro elemento (ou seja, o elemento mais antigo) da fila F. O comando Entra-na-Fila(v,F) insere v no fim da fila F.

O segredo do funcionamento do algoritmo está na fila FIFO de vértices.  Como os vértices são visitados em ordem de busca em largura,  temos as seguintes propriedades no início de cada execução do bloco de linhas 6-10:

  1. para todo vértice v,  se dist[v] < ∞ então dist[v] é a distância de rv  e
  2. para todo arco -uv, se dist[u] < ∞ e dist[v] = ∞ então u está na fila.

Portanto, quando a execução do algoritmo termina, dist[s] é a distância de r a s para todo s.

Para mostrar que os invariantes i e ii de fato valem no início de cada iteração é preciso fazer a seguinte observação auxiliar sobre a estrutura da fila.  Digamos que q1 é o primeiro elemento da fila, q2 o segundo, etc., e qk é o último.  Então, se denotarmos dist[q1] por d, teremos

  1.   d < ∞,
  2.   dist[q1]  ≤  dist[q2]  ≤  …  ≤  dist[qk]  ≤  d+1   e
  3.   dist[x] ≤ d  ou dist[x] = ∞  para todo x que esteja fora da fila.

Exercícios

  1. Aplique o algoritmo Distâncias ao exemplo discutido na página Busca em Largura
  2. Mostre que no fim da execução algoritmo Distâncias tem-se dist[v] ≤ dist[u]+1   para todo arco uv.  (Suponha que ∞ + 1 = ∞.)

Consumo de tempo do algoritmo

O algoritmo Distâncias é linear:  o consumo de tempo do algoritmo é o mesmo do algoritmo Busca-em-Largura, ou seja,

Ο(n+m) ,

sendo m o número de arcos do digrafo.

Exercícios

  1. Bom!  Escreva uma versão do algoritmo Distâncias supondo que o digrafo tem vértices 1, 2, … , n e é representado por sua matriz de adjacência.  Mostre que o consumo de tempo dessa versão é  Ο(n2).

Apêndice: passeios mínimos

Seria muito interessante obter não só a distância de um vértice r a um vértice s como também um passeio que realiza essa distância, ou seja, um passeio de comprimento mínimo de rs.  Poderíamos tratar desse assunto imediatamente, mas eu prefiro fazer isso mais tarde, depois que tiver discutido arborescências.

Valid HTML 4.01 Strict Valid CSS!