GRAFOS: Distancias

Um caminho C de um vértice r a um vértice s é 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 é k significa duas coisas: (1) existe um caminho de r a s com exatamente k arcos e (2) não existe caminho de r a s com menos que k 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"] .

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.

Algoritmo das distâncias

Para resolver o problema, basta modificar ligeiramente o algoritmo de busca em largura. Para cada vértice v, a distância de r a v será v–>dist. Se a distância de r a v ainda não está definida, diremos que v–>dist vale –1. [Faria mais sentido dizer que v–>dist vale infinito

nesse caso. Poderíamos (por que?) usar o número de vértices do grafo, n, para representar infinito

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:

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

Exercícios

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 v–>dist + 1 arcos. Prove também que a cada passagem pela linha 7 não existe caminho de r a w com menos que v–>dist + 1 arcos. Sugestão: Quais os valores de dist ao longo da fila? Digamos que os vértices da fila são u1, u2, . . . , up , nesta ordem; que cara tem a seqüência de números u1–>dist, u2–>dist, . . . , up–>dist?
Mostre que cada vértice entra no máximo uma vez na fila.
[Obrigatório] 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 determinar 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 = g–>n;  v0 = g–>vertices;
for (v = v0; v < v0+n; v++)  v–>dist = –1;
r–>dist = 0;

for (d = 0; d < n; d++)
   for (v = v0; v < v0+n; v++)
      if (v–>dist == d)
         for (a = v–>arcs; a != NULL; a = a–>next)
            if (a–>tip–>dist == –1)  
               a–>tip–>dist = 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: Determinar 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 , determinar 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

Escreva uma função caminho_mínimo que recebe um grafo g e vértices r e s e determine 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, r–>suc, r–>suc–>suc, . . . , s
deverá ser a seqüê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 r–>suc == NULL . (Como deve ser definido s–>suc 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 é a–>len.) 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. O módulo é um tanto complexo porque é muito genérico (permitido, entre outras coisas, que alguns arcos tenham comprimento negativo).

Exercícios

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 é a–>len. 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 entre dois vértices de um grafo cujos arcos têm comprimentos arbitrários, possivelmente negativos.
[Desafio] Dados vértices r e s de um grafo, determine 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.

Distâncias

Algoritmo das distâncias

Exercícios

Algoritmo do caminho mínimo

Exercícios

O módulo GB_DIJK do SGB

Exercícios