Algoritmos para Grafos  |  Índice

Algoritmo de caminhos mínimos

O capítulo anterior fez uma introdução geral ao problema do caminho de comprimento mínimo e mostrou que ele é essencialmente equivalente ao problema da árvore de caminhos curtos.  Aquele capítulo também mostrou um algoritmo para a restrição do problema a grafos acíclicos.  O presente capítulo trata de um algoritmo geral, para grafos arbitrários.

O algoritmo

Como já dissemos no capítulo Caminhos de comprimento mínimo, uma árvore de caminhos curtos, ou SPT (= shortest-paths tree), de um grafo G é uma subárvore radicada geradora T de G tal que todo caminho em T a partir da raiz é mínimo em G.

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 é 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 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 à da permutação topológica que guia a execução do algoritmo especial para dags (capítulo Caminhos de comprimento mínimo). Mas, diferentemente do que acontece naquele algoritmo, 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.

A operação  dist[w] = dist[v] + 1  é uma relaxação do arco v-w.

Implementação do algoritmo

A implementação do algoritmo dos caminhos mínimos é uma adaptação da função GRAPHbfs() de busca BFS.  O resultado é a função GRAPHspt(). No fim da execução da função, o vetor dist[] é um potencial relaxado, embora a função não procure arcos tensos explicitamente, como acontece na função que calcula uma SPT num dag.

/* Esta função recebe um grafo G
   e um vértice s de G
   e armazena em pa[]
   o vetor de pais de uma SPT
   do sub­grafo induzido pelos vértices 
   que estão ao alcance de s.
   A SPT tem raiz s e
   as distâncias a partir de s
   são armazenadas no vetor dist[].
   O espaço para os vetores pa[] e dist[]
   deve ser alocado pelo usuário.
   Esta implementação supõe que o grafo G 
   é representado por listas de adjacência. 
   (Código inspirado no programa 18.9 de Sedgewick.) */

void GRAPHspt( Graph G, vertex s, 
                         int *dist, vertex *pa)
{ 
   const int INFINITY = G->V;
   for (vertex v = 0; v < G->V; ++v) 
      dist[v] = INFINITY, pa[v] = -1;
   dist[s] = 0, pa[s] = s;
   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.

Desempenho.  A análise do desempenho de GRAPHspt() é 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 GRAPHspt() para grafos representados por matriz de adjacências consome tempo proporcional a V² no pior caso.  Se nos restrigirmos a grafos densos, esse consumo é considerado linear.

Exemplo A.  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 GRAPHspt() 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ência, os vértices aparecem em ordem crescente de nomes.)

Exemplo B.  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 GRAPHspt() 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ência, os vértices aparecem em ordem crescente de nomes.)  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 abaixo):

dist[queue[]]

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

Por que o algoritmo está correto?

Para provar que a função GRAPHspt() está correta, vamos recorrer à condição suficiente de minimalidade descrita no capítulo Caminhos de comprimento mínimo. O vetor dist[] fará o papel de potencial relaxado. 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 DAGspt().

Agora que temos os invariantes, podemos analisar a última iteração, que começa com a fila vazia.  Para simplificar ligeiramente a discussão, vamos supor que todos os vértices do grafo estão ao alcance de s.  A análise se reduz a três observações:

• Primeira observação: de acordo com o invariante 2, nenhum arco começa em T e termina fora de T. Logo, todos os vértices que estão ao alcance de s pertencem a T.  Portanto, T é um sub­grafo gerador de G.
• Segunda observação: o potencial dist[] é relaxado. De fato, os invariantes 1 e 2 garantem que todo arco com ponta inicial em T tem ponta final em T e portanto está relaxado.
• Terceira observação: para cada vértice t de T, o caminho de s a t em T tem comprimento dist[t], conforme o exercício Distâncias na árvore acima.  De acordo com a condição suficiente de minimalidade do capítulo Caminhos de comprimento mínimo, essa observação, junto com as anteriores, garante que o caminho de s a t em T é mínimo em G.

Portanto, no fim da execução do algoritmo, T é uma árvore de caminhos curtos 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 s a t em G.  Isso prova que GRAPHspt() está correto.