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.
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 s a r. A distância de r a s é infinita se não existe passeio algum de r a s, 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".
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) |
| 11 o para u ← 1 até n faça |
| 12 oooo dist[u] ← ∞ |
| 13 o dist[r] ← 0 |
| 14 o F ← Cria-Fila(r) |
| 15 o enquanto F não estiver vazia faça |
| 16 oooo u ← Sai-da-Fila(F) |
| 17 oooo para cada v em Adj[u] faça |
| 18 ooooooo se dist[v] = ∞ |
| 19 oooooooooo 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:
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
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.
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 r a s. Poderíamos tratar desse assunto imediatamente, mas eu prefiro fazer isso mais tarde, depois que tiver discutido arborescências.