Distâncias em grafos

Um caminho C de um vértice r a um vértice s em um grafo é mínimo se não existe outro caminho de r a s que tenha menos arcos que C. (Exercício: Mostre que todo caminho mínimo é simples.)

A distância de um vértice r a um vértice s é o número de arcos de um caminho mínimo de r a s. (Cuidado: não faz sentido dizer a menor distância ou a distância mínima: distância já é mínima por definição.) Portanto, dizer que a distância de r a s é d significa duas coisas: (1) existe um caminho de r a s com exatamente d arcos e (2) não existe caminho de r a s com menos que d arcos. Note que a distância de r a s pode ser diferente da distância de s a r. (Por isso evito dizer distância entre r e s.)

Problema das Distâncias: Dados vértices r e s, calcular a distância de r a s.

Se não existe caminho algum de r a s, ou seja, se s não está no território de r, podemos dizer que a distância é infinita.

Exercícios 1

Mostre que a distância de r a s é d se e somente se (1) existe um caminho de r a s com exatamente d arcos e (2) todo caminho de r a s tem d ou mais arcos.

Algoritmo das distâncias

Para resolver o problema das distâncias, basta modificar ligeiramente o algoritmo de busca em largura. Para cada vértice v, a distância de r a v será vdist. Se a distância de r a v ainda não está definida, diremos que vdist vale −1. (Faria mais sentido dizer que vdist vale ∞ nesse caso. Poderíamos (por que?) usar o número de vértices do grafo, n, para representar ∞.)

Cada iteração começa com uma fila de vértices ativos; no início da primeira iteração, r é o unico vértice da fila. Cada iteração consiste no seguinte:

se a fila está vazia

então pare

senão seja v o primeiro vértice da fila

senão para cada vértice w adjacente a v

senão se wdist ≡ −1

senão então wdist = vdist + 1

senão então insira w no final da fila

senão retire v da fila

A fila garante que dá tudo certo: a cada passagem pela linha 7, wdist é a distância correta de r a w. No fim do algoritmo, wdist ≡ −1 se e só se w está fora do território de r.

Exercícios 2

Para verificar que o algoritmo das distâncias está correto, prove que a cada passagem pela linha 7 existe um caminho de r a w com vdist + 1 arcos. Prove também que a cada passagem pela linha 7 não existe caminho de r a w com menos que vdist + 1 arcos. (Sugestão: Quais os valores de dist ao longo da fila? Digamos que os vértices da fila são u₁, u₂, … , u_p, nesta ordem; que cara tem a sequência de números u₁dist, u₂dist, … , u_pdist?)
Mostre que cada vértice entra no máximo uma vez na fila.
Implemente o algoritmo das distâncias: escreva uma função C que receba um grafo e um par r, s de seus vértices e devolva a distância de r a s.
Analise e comente o seguinte algoritmo, que promete encontrar a distância de um dado vértice r a cada um dos demais vértices de um grafo g.

#define dist x.I
n = gn; v0 = gvertices;
for (v = v0; v < v0 + n; v++) vdist = −1;
rdist = 0;
for (d = 0; d < n; d++)
for (v = v0; v < v0 + n; v++)
if (vdist ≡ d)
for (a = varcs; a ≠ NULL; a = anext)
if (atipdist ≡ −1)
atipdist = d + 1;
[Bom!] Suponha que nosso grafo tem dois tipos de arestas: vermelhas e brancas. Digamos que um caminho é alternante se sua primeira, terceira, quinta, etc. arestas são brancas enquanto a segunda, quarta, etc. são vermelhas. Um caminho alternante de um vértice r a um vértice s é mínimo se não existe outro caminho alternante de r a s que tenha menos arcos. A distância alternante de um vértice r a um vértice s é o número de arcos de um caminho alternante mínimo de r a s. Problema: Encontrar a distância alternante de um vértice r a um vértice s.

Algoritmo do caminho mínimo

Problema: Dados vértices r e s, encontrar um caminho mínimo de r a s. Como já vimos, o número de arcos de um tal caminho é a distância de r a s.

Para encontrar um caminho mínimo, faça uma adaptação do algoritmo das distâncias visto acima. O algoritmo calculará uma arborescência que cobrirá o território de r. Se a arborescência atingir s, basta voltar ao longo dos arcos da arborescência (de s para o seu predecessor e assim em diante) até chegar ao vértice r. Esse percurso é o inverso do caminho desejado.

Exercícios 3

Escreva uma função caminho_mínimo que receba um grafo g e vértices r e s e encontre um caminho mínimo de r a s em g. Para descrever o caminho, basta especificar o sucessor de cada vértice ao longo do caminho. Use um utility field suc: ao terminar a execução do algoritmo, r, rsuc, rsucsuc, … , s deverá ser a sequência de vértices de um caminho mínimo de r a s. Se não houver caminho algum de r a s, deveremos ter rsuc ≡ NULL. (Como deve ser definido ssuc para que o algoritmo funcione corretamente até mesmo quando r ≡ s?)

O módulo GB_DIJK do SGB

Suponha que cada arco do grafo tem um comprimento (= length), que é um número inteiro não-negativo. (Na estrutura de dados do SGB, o comprimento de um arco a é alen.) Re-defina o conceito de distância de maneira apropriada: o comprimento de um caminho deverá ser a soma dos comprimentos de seus arcos. Podemos agora perguntar pela distância de um vértice r a um vértice s. Podemos também perguntar por um caminho mínimo (nesse novo sentido) de r a s.

O módulo GB_DIJK do SGB resolve esses problemas e implementa o célebre algoritmo de Dijkstra. O módulo é um tanto complexo porque é muito genérico, permitindo, entre outras coisas, que alguns arcos tenham comprimento negativo.

Exercícios 4

Escreva uma função que receba um grafo g e dois vértices r e s e devolva um caminho de comprimento mínimo de r a s. O comprimento de um caminho é a soma dos comprimentos dos seus arcos. O comprimento de cada arco a é alen. Sua função pode supor que o grafo não tem arcos de comprimento negativo. O código de sua função deve ser extraído do módulo GB_DIJK do SGB: elimine as partes irrelevantes do GB_DIJK mas preserve, tão fielmente quanto possível, as partes relevantes (pedaços de código, nomes de variáveis, utility fields, etc.)
[Desafio] Calcule a distância de um vértice r a um vértice s em um grafo cujos arcos têm comprimentos arbitrários, possivelmente negativos.
[Desafio] Dados vértices r e s de um grafo, encontre um caminho de r a s que tenha número máximo de arcos. O módulo FOOTBALL do SGB tenta resolver um problema semelhante no grafo gerado pela função games.