Algoritmos para Grafos  |  Índice

Algoritmo de caminhos mínimos

Um capítulo anterior fez uma introdução geral ao problema do caminho de comprimento mínimo e mostrou um algoritmo que resolve o problema em grafos acíclicos.  O presente capítulo discute um algoritmo para grafos arbitrários.

TinyNetwork-x.png

O algoritmo

O problema do caminho mínimo, já enunciado no capítulo Caminhos mínimos consiste no seguinte:  Dados vértices st de um grafo G, encontrar um caminho mínimo em G que tenha origem s e término t.

figs/Sedgewick-Wayne/spt-from-0.png

Para resolver o problema, basta adaptar o algoritmo de busca em largura de modo que a numeração dos vértices represente as distâncias a partir de s.  O algoritmo resultante calcula, de uma só vez, todos os caminhos mínimos que têm origem s. O conjunto de todos esses caminhos é representado por uma árvore de busca em largura, que chamaremos árvore de caminhos mínimos (= shortest paths tree). Ela tem raiz s e contém todos os vértices ao alcance de s.

O algoritmo é iterativo. Cada iteração começa com  (1) uma árvore radicada com raiz s, representada por um vetor de pais pa[ ],  (2) um vetor dist[ ] que dá a distância de s a cada vértice da árvore,  e  (3) uma fila (= queue) de vértices da árvore.   Cada iteração consiste no seguinte:

No começo da primeira iteração, s é o único vértice da árvore, dist[s] vale 0, e a fila contém s e nada mais.  O processo iterativo termina quando a fila fica vazia.

A fila de vértices tem um papel semelhante à permutação topológica que guia a execução do algoritmo especial para dags (veja o capítulo Caminhos mínimos). Graças à ordem imposta pela fila, cada elemento do vetor dist[ ] é definido uma só vez: para cada vértice w, dist[w] é definido em alguma iteração e nunca mais alterado.

Depois da execução do algoritmo, um caminho mínimo de st pode ser obtido da seguinte maneira:  Se o vértice t não pertence à árvore radicada — ou seja, se pa[t] está indefinido — então não existe caminho algum de st. Senão, o vetor pa[ ] contém a descrição de um caminho mínimo de st e dist[t] é o comprimento desse caminho.

Exercícios 1

  1. ★ Como começa cada iteração do algoritmo dos caminhos mínimos? (Cuidado! Não se trata de descrever as ações que ocorrem no começo da iteração. Trata-se de saber que informações estão disponíveis no início de uma iteração genérica, antes que a execução da iteração comece.)
  2. Considere o grafo definido pelos arcos 0-2 0-3 0-4 1-2 1-4 2-4 3-4 3-5 4-5 5-1.  Calcule todas as distâncias a partir do vértice 0.
  3. Considere o grafo não-dirigido definido pelas arestas  0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5.  Calcule uma árvore de caminhos mínimos com raiz 0.  Exiba o estado da fila e dos vetores dist[] e pa[] no início de cada iteração.

Implementação do algoritmo

Para implementar o algoritmo dos caminhos mínimos, basta adaptar a função GRAPHbfs() do capítulo Busca em largura:

/* Esta função recebe um grafo G
   e um vértice s de G
   e armazena em pa[]
   o vetor de pais de uma árvore de caminhos mínimos
   com raiz s.
   (Se um vértice v não está ao alcance de s,
   teremos pa[v] == -1.)
   As distâncias a partir de s
   são armazenadas no vetor dist[].
   O espaço para os vetores pa[0..V-1] e dist[0..V-1]
   deve ser alocado pelo usuário.
   Esta versão da função supõe que o grafo G 
   é representado por listas de adjacência. 
   (Código inspirado no programa 18.9 de Sedgewick.) */
void GRAPHminPaths( Graph G, vertex s, 
                    int *dist, vertex *pa) 
{ 
   const int INFINITY = G->V;
   for (vertex v = 0; v < G->V; ++v) 
      pa[v] = -1, dist[v] = INFINITY;
   pa[s] = s, dist[s] = 0;
   QUEUEinit( G->V);
   QUEUEput( s); 

   while (!QUEUEempty( )) {
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         vertex w = a->w; 
         if (dist[w] == INFINITY) { 
            dist[w] = dist[v] + 1;
            pa[w] = v;
            QUEUEput( w); 
         }
   }
   QUEUEfree( ); 
}

A constante INFINITY é uma boa representação de ∞ pois seu valor é maior que o comprimento de qualquer caminho no grafo.  Se um vértice v não estiver ao alcance de s, teremos dist[v] ≡ INFINITY até o fim da execução da função.

As funções auxiliares que manipulam a fila — QUEUEget(), QUEUEput(), etc. — são as mesmas que já usamos na função de busca em largura.  A fila foi dimensionada corretamente na linha QUEUEinit( G->V) pois cada vértice de G entra na fila no máximo uma vez e portanto a fila não precisa de mais do que G->V posições.

Desempenho.  A análise do desempenho de GRAPHminPaths() é idêntica à análise do desempenho da função GRAPHbfs() de busca em largura. Se o grafo tem V vértices e A arcos, a função consome  V + A  unidades de tempo no pior caso.  Esse tempo é proporcional ao tamanho do grafo e portanto podemos dizer que a função é linear.   A variante de GRAPHminPaths() para grafos representados por matriz de adjacências consome tempo proporcional a V2 no pior caso.  Se nos restrigirmos a grafos densos, esse consumo é considerado linear.

figs/mine/diwheel6-k-gray.png

Exemplo B.  Considere o grafo definido pelos arcos 0-2 0-3 0-4 1-2 1-4 2-4 3-4 3-5 4-5 5-1 .  Submeta o grafo à função GRAPHminPaths() com segundo argumento 0.  Veja o estado da fila, e o estado dos vetores dist[] e pa[] (com * no lugar de INFINITY e - no lugar de -1) no início de cada iteração:

queue[]        dist[]         pa[]          
               0 1 2 3 4 5    0 1 2 3 4 5
0              0 * * * * *    0 - - - - -
  2 3 4        0 * 1 1 1 *    0 - 0 0 0 -
    3 4        0 * 1 1 1 *    0 - 0 0 0 -
      4 5      0 * 1 1 1 2    0 - 0 0 0 3
        5      0 * 1 1 1 2    0 - 0 0 0 3
          1    0 3 1 1 1 2    0 5 0 0 0 3
               0 3 1 1 1 2    0 5 0 0 0 3

(Estou supondo que, em cada lista de adjacências, os vértices aparecem em ordem crescente de nome.)

figs/Sedgewick-Wayne/GraphRepDFSex-tinyCG-x.png

Exemplo C.  Seja G o grafo não-dirigido definido pelas arestas  0-1 0-2 0-5 2-1 2-3 2-4 3-4 3-5.  Submeta G à função GRAPHminPaths() com segundo argumento 0.  Veja o estado da fila, e o estado dos vetores dist[] e pa[] no início de cada iteração:

queue[]        dist[]         pa[]          
               0 1 2 3 4 5    0 1 2 3 4 5
0              0 * * * * *    0 - - - - -
  1 2 5        0 1 1 * * 1    0 0 0 - - 0
    2 5        0 1 1 * * 1    0 0 0 - - 0
      5 3 4    0 1 1 2 2 1    0 0 0 2 2 0
        3 4    0 1 1 2 2 1    0 0 0 2 2 0
          4    0 1 1 2 2 1    0 0 0 2 2 0
               0 1 1 2 2 1    0 0 0 2 2 0

(Estou supondo que, em cada lista de adjacências, os vértices aparecem em ordem crescente de nome.)  Veja os valores de dist[] nos vértices da fila no início de sucessivas iterações (compare com o exercício Propriedades da fila):

figs/Sedgewick-Wayne/BFSTrace6-x.png
dist[queue[]]

0              
  1 1 1        
    1 1        
      1 2 2    
        2 2    
          2    

Exercícios 2

  1. Instâncias extremas.  A função GRAPHminPaths() produz o efeito desejado se G tem apenas 1 vértice?  E se G não tem arcos?  E se G é uma árvore radicada com 2 vértices?  E se G é uma árvore radicada com 3 vértices?
  2. Matriz de adjacências.  Adapte a função GRAPHminPaths() a grafos representados por matriz de adjacências.
  3. Considere o grafo não-dirigido definido pelas arestas  8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.  Suponha que o grafo é representado por matriz de adjacência. Calcule a distância do vértice 0 a cada um dos demais.  Faça uma figura da árvore de caminhos mínimos.   Repita o exercício supondo que o grafo é representado por listas de adjacência construídas inserindo as arestas, na ordem dada, num grafo inicialmente vazio.
  4. Código compacto.  Escreva uma versão de GRAPHminPaths() que incorpore o código das funções de manipulação da fila. (A fila deve ser implementada em um vetor.) Escreva código simples, sem variáveis e instruções supérfluas.
  5. Distâncias na árvore.  Seja T a árvore radicada representada pelo vetor pa[] no código de GRAPHminPaths().  Mostre que  dist[v]+1 ≡ dist[w]  para cada arco v-w de T.  Deduza daí que, para cada w, dist[w] é o comprimento do único caminho de sw em T.
  6. Propriedades da fila.  Seja v, q1, … , qk a sequência dos vértices que estão na fila no início de uma iteração qualquer de GRAPHminPaths().  Adote a abreviatura temporária d para dist e mostre que

    d[v]  ≤  d[q1] ≤ ... ≤ d[qk]  ≤  d[v]+1.

    Agora considere a árvore radicada T representada pelo vetor pa[] e mostre que d[u] ≤ d[v] para cada u em T que não está na fila.  (Essas propriedades são usadas na prova da correção do algoritmo.)

  7. ★ Depois de executar a função GRAPHminPaths() com argumentos Gs, seja  X  o conjunto dos vértices x para os quais pa[x] ≠ -1.  Descreva o leque de saída de X, ou seja, o conjunto de arcos que têm ponta inicial em X e ponta final fora de X.
  8. Suponha dado o vetor pa[] que representa uma árvore de caminhos mínimos de um grafo G.  Escreva uma função que receba um vértice t e devolva a distância em G da raiz da árvore até t. Se t estiver na árvore, imprima o caminho na árvore da raiz até t.
  9. Atualize sua biblioteca.  Acrescente a função GRAPHminPaths() à biblioteca GRAPHlists mencionada no capítulo Estruturas de dados para grafos.  (Quem sabe é melhor acrescentar a versão sugerida no exercício Código compacto.) Repita o exercício para a biblioteca GRAPHmatrix.
  10. Caminhos mínimos em grafos não-dirigidos.  Escreva uma função que calcule caminhos mínimos a partir de um dado vértice s em um grafo não-dirigido.  Seu código é mais simples que o de GRAPHminPaths()?

Por que o algoritmo está correto?

Para provar que a função GRAPHminPaths() está correta, vamos recorrer ao certificado de minimalidade descrito na seção Arcos relaxados e potencial viável do capítulo Caminhos mínimos. O vetor dist[] fará o papel de potencial. Vale lembrar que um arco v-w está relaxado se dist[v]+1 ≥ dist[w].

Seja T a árvore radicada representada por pa[]. Com essa notação, as seguintes propriedades valem no início de cada iteração, sendo pois invariantes:

  1. todo arco com ambas as pontas em T está relaxado em relação a dist[] e
  2. para cada arco x-y, se x está em T e y está fora de T então x está na fila.

Provar os invariantes 1 e 2 é um excelente exercício. Note que o invariante 1 não é óbvio, uma vez que o algoritmo não verifica explicitamente a relaxação de cada arco, como faz DAGminPaths().

Agora que temos os invariantes, podemos analisar a última iteração, que começa com a fila vazia.  A análise se reduz a três observações:

Portanto, no fim da execução do algoritmo, T é uma árvore de caminhos mínimos com raiz s, como já havíamos antecipado.  Ademais, para cada vértice t de G, o número dist[t] é a distância de st em G.  Isso prova que GRAPHminPaths() está correto.

Exercícios 3

  1. Prova dos invariantes.  Prove os invariantes 1 e 2 do processo iterativo na função GRAPHminPaths().  As provas dependem das propriedades da fila discutidas num exercício acima. Também dependem das propriedades discutidos no exercício Distâncias na árvore
  2. Deduza dos invariantes do processo iterativo na função GRAPHminPaths() que no início de cada iteração, para cada vértice t na árvore T, a distância de st em G é exatamente dist[t].

Exercícios 4

  1. Caminhos mínimos a partir de um conjunto.  Generalize o código de GRAPHminPaths() para resolver o seguinte problema:  dado um conjunto não vazio S de vértices, determinar, para cada vértice t do grafo, um caminho de comprimento mínimo dentre os que começam em S e terminam em t.  (O resultado desse exercício é usado, por exemplo, no algoritmo dos caminhos de aumento para o problema do emparelhamento máximo.)
  2. Grafos que mudam com o tempo.  Sejam dist[] e pa[] os vetores calculados pela função GRAPHminPaths() com argumentos Gs.  (1) Se um arco v-w for removido, dist[] continua sendo o vetor de distâncias do grafo?  (2) Se a direção de um arco v-w for invertida (ou seja, v-w for trocado por w-v), dist[] continua sendo o vetor de distâncias do grafo?  (3) Se um novo arco x-y for inserido no grafo, dist[] continua sendo o vetor de distâncias do grafo?  Dê algoritmos eficientes para responder essas perguntas.
  3. [Sedgewick 18.55]  Diâmetro de grafo não-dirigido.  Denote por d(s,t) a distância de um vértice s a um vértice t de um grafo não-dirigido.  O diâmetro do grafo é o valor máximo da expressão  d(s,t)  com s e t variando no conjunto de todos os vértices.  Escreva uma função UGRAPHdiameter() que calcule o diâmetro de um grafo não-dirigido.
  4. Vértices centrais. Um vértice s de um grafo não-dirigido é central se minimiza maxt d(s,t), sendo d(s,t) a distância de st.  Escreva uma função que devolva um vértice central de qualquer grafo não-dirigido conexo.
  5. Centros de árvores. Mostre que toda árvore tem no máximo dois vértices centrais, e se tiver dois então eles são adjacentes.  Escreva uma função que calcule todos os vértices centrais de uma árvore dada.
  6. Fenômeno small world.  Estude a evolução da distância média entre dois vértices diferentes em grafos não-dirigidos aleatórios com 10000 vértices em função do número de arestas. Repita o exercício com número maior de vértices. (A propósito, veja a pergunta What's the significance of the cliché six degrees of separation? no Quora.)
  7. Fenômeno small world.  Considere grafos não-dirigido aleatórios construídos da seguinte maneira:  comece com um grafo não-dirigido G produzido pela função UGRAPHclosePoints(); depois, para cada vértice v de G, acrescente k arestas do tipo v-w sendo w escolhido aleatoriamente dentre todos os demais vértices de G.  Digamos, para efeito deste exercício, que grafos não-dirigidos assim construídos são do tipo WS (referência a Watts e Strogatz).  Escreva uma função UGRAPHsmallWorld() que calcule a distância média entre dois vértices distintos de um grafo do tipo WS. Se o grafo for desconexo, a distância média será infinita. (A propósito, veja a pergunta What's the significance of the cliché six degrees of separation? no Quora.)

Perguntas e respostas