Algoritmos em Grafos | Livros | WWW | Índice de Termos

 

Distâncias

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

Problema das Distâncias:  Dados vértices  r  e  s , determinar 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.

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:

1

2

3

4

5

6

7

8

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  w–>dist == –1

senão então  w–>dist = v–>dist + 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,  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

  1. 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–>distu2–>dist,  . . . ,  up–>dist?

  2. Mostre que cada vértice entra no máximo uma vez na fila.

  3. [Obrigatório]  Implemente o algoritmo das distâncias:  escreva uma função C que receba um grafo e um par  rs  de seus vértices e devolva a distância de r a s.  

  4. 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;
    

  5. [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 sProblema: 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

  1. 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, 

    rr–>suc, r–>suc–>suc, . . . , s

    deverá ser a seqüência de vértices de um caminho mínimo de rs.  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

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

  2. [Desafio]  Calcule a distância entre dois vértices de um grafo cujos arcos têm comprimentos arbitrários, possivelmente negativos.

  3. [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.

 


Apontador.com.br: Navegação no mapa da cidade de São Paulo. Encontra caminho mínimo entre dois pontos da cidade.
www.ime.usp.br/~pf/algoritmos_em_grafos/
Last modified: Mon Sep 18 13:03:44 BRT 2017
Paulo Feofiloff
IME-USP