Algoritmos para Grafos  |  Índice

Algoritmo de Dijkstra

Este capítulo discute um algoritmo para o problema da CPT sob custos positivos. (Veja uma introdução geral ao problema no capitulo Caminhos de custo mínimo.)

Vale lembrar que uma árvore de caminhos baratos, ou CPT (= cheapest-paths tree), é uma sub­árvore radicada geradora T de G tal que todo caminho em T que começa na raiz tem custo mínimo em G.  Como observamos no capítulo introdutório, uma grafo com custos positivos tem uma CPT com raiz s se e somente se todos os seus vértices estão ao alcance de s.  Para escamotear essa condição, podemos trabalhar com o sub­grafo induzido pelos vértices que estão ao alcance de s.

Um algoritmo para o problema foi descoberto por Edsger W. Dijkstra [pronuncie algo entre Dêcstra e Dêicstra] e publicado em 1959.  O algoritmo é simples, mas sua implementação eficiente apresenta dificuldades inesperadas. A solução dessas dificuldades ensina boas lições de programação.

Preliminares

Dado um grafo G com custos positivos nos arcos e um vértice s, o algoritmo de Dijkstra faz crescer uma subárvore radicada em G, a partir do vértice s, até que ela englobe todos os vértices que estão ao alcance de s. Para simplificar a discussão, vamos supor que todos os vértices de G estão ao alcance de s. Assim, ao final da execução do algoritmo, a sub­árvore torna-se geradora.

Para discutir os detalhes, usaremos o conceito de franja. A franja (= fringe) de uma sub­árvore radicada T de G é o conjunto de todos os arcos do grafo que têm ponta inicial em T e ponta final fora de T. Em outras palavras, a franja de T é o leque de saída do conjunto de vértices de T.

Nossa primeira descrição do algoritmo de Dijkstra será feita num nível de abstração bastante alto. O algoritmo é iterativo. Cada iteração começa com uma árvore radicada T, com raiz s, e o vetor dist[ ] das distâncias em T a partir de s. (Portanto, dist[v] é o custo do único caminho de s a v em T se v não pertence a T e dist[v] é infinito em caso contrário.)  No começo da primeira iteração, s é o único vértice de T e dist[s] vale 0.  O processo iterativo consiste no seguinte:  enquanto a franja de T não estiver vazia,

1. escolha, na franja de T, um arco x-y que minimize dist[x] + c_xy ,
2. acrescente o arco x-y e o vértice y a T  e
3. faça dist[y] = dist[x] + c_xy .

Nessa descrição,  c_xy  é o custo do arco x-y.  Depois do passo 1, podemos dizer, informalmente, que y é o vértice fora de T que está mais perto de s.

Exemplo A.  Considere o grafo com custos nos arcos definido pela tabela a seguir.  Queremos encontrar uma CPT com raiz 0 no grafo.

0-1 0-2 1-3 1-4 2-3 2-4 3-1 3-5 4-5
 10  20  70  80  50  60   0  10  10

Veja o rastreamento da execução do algoritmo de Dijkstra. No início de cada iteração, registramos o conjunto de vértices da árvore radicada T, os valores de dist[ ] (com * para indicar infinito), e os arcos da franja de T :

              dist[]                
T             0  1  2  3  4  5   franja 

0             0  *  *  *  *  *   0-1 0-2
0 1           0 10  *  *  *  *   0-2 1-3 1-4
0 1 2         0 10 20  *  *  *   1-3 1-4 2-3 2-4
0 1 2 3       0 10 20 70  *  *   1-4 2-4 3-5
0 1 2 3 4     0 10 20 70 80  *   3-5 4-5
0 1 2 3 4 5   0 10 20 70 80 80      

O arco da franja que será acrescentado a T na próxima iteração está pintado de vermelho.  A CPT calculada pelo algoritmo pode ser resumida apagando as colunas apropriadas na tabela que descreve o grafo:

0-1 0-2         2-3 2-4 3-5
 10  20          50  60  10

Exemplo B.  Queremos encontrar uma CPT com raiz 0 no grafo com custos nos arcos definido a seguir.

0-2 0-3 0-4 2-4 3-4 3-5 4-1 4-5 5-1 1-2
 70  50  30  10  10  20   0  30  50  30

Veja o rastreamento da execução do algoritmo de Dijkstra. No início de cada iteração, registramos o conjunto de vértices da árvore radicada T, os valores de dist[ ] e os arcos da franja:

T             dist[]             franja

0             0  *  *  *  *  *   0-2 0-3 0-4
0 4           0  *  *  * 30  *   0-2 0-3 4-1 4-5
0 4 1         0 30  *  * 30  *   0-2 0-3 4-5 1-2
0 4 1 3       0 30  * 50 30  *   0-2 4-5 1-2 3-5
0 4 1 3 5     0 30  * 50 30 60   0-2 1-2
0 4 1 3 5 2   0 30 60 50 30 60 

O arco da franja que será acrescentado a T na próxima iteração está pintado de vermelho.  A CPT calculada pelo algoritmo pode ser resumida apagando as colunas apropriadas na tabela que descreve o grafo:

    0-3 0-4             4-1 4-5     1-2
     50  30               0  30      30

O algoritmo

A implementação ingênua do algoritmo de Dijkstra é ineficiente porque cada iteração recalcula a franja da árvore radicada, embora essa franja seja quase igual à da iteração anterior.  Para obter uma implementação mais eficiente, é preciso acrescentar à árvore os melhores arcos da franja, ainda que eles não sejam definitivos e possam ser substituídos nas próximas iterações.  Essa ideia leva a uma segunda descrição do algoritmo, num nível de abstração mais baixo.

Nossa segunda descrição do algoritmo de Dijkstra depende do conceito de vértice maduro. Um vértice do grafo G é considerado maduro (= mature) se o seu leque de saída já foi examinado. Todos os demais vértices de G são considerados imaturos. É claro que todo vértice maduro pertence à árvore em construção.

Cada iteração do algoritmo começa com um vetor de pais pa[] que representa uma árvore radicada T com raiz s, um potencial dist[] em G, e um conjunto de vértices maduros.  No começo da primeira iteração, s é o único vértice de T, todos os vértices imaturos, dist[s] vale 0, e dist[v] vale ∞ para todo v diferente de s.  O processo iterativo consiste no seguinte:  enquanto T tiver vértices imaturos,

1. seja y um vértice imaturo de T que minimiza dist[];
2. para cada arco y-z de G que está tenso
   faça  dist[z] = dist[y] + c  e  pa[z] = y;
3. declare y maduro.

No passo 2, c é o custo do arco y-z.  Convém lembrar que, por definição, um arco y-z está tenso em relação a dist[] se dist[y]+c < dist[z], está relaxado se dist[y]+c ≥ dist[z], e está justo se dist[y]+c ≡ dist[z].  Em particular, todo arco y-z que tem dist[y] < ∞ e dist[z] ≡ ∞ está tenso.

Exemplo C.  Voltamos a examinar o exemplo A. Veja novamente a lista de arcos do grafo e seus custos.

0-1 0-2 1-3 1-4 2-3 2-4 3-1 3-5 4-5
 10  20  70  80  50  60   0  10  10

Aplique o algoritmo de Dijkstra a partir do vértice 0. Veja o conjunto de vértices de T e o estado dos vetores pa[] e dist[] no início de sucessivas iterações. A cor vermelha indica vértices maduros, - indica valores indefinidos, e * indica ∞:

              pa[]            dist[]
T             0 1 2 3 4 5   0  1  2  3  4  5

0             0 - - - - -   0  *  *  *  *  *
0 1 2         0 0 0 - - -   0 10 20  *  *  *
0 1 2 3 4     0 0 0 1 1 -   0 10 20 80 90  *
0 1 2 3 4     0 0 0 2 2 -   0 10 20 70 80  *
0 1 2 3 4 5   0 0 0 2 2 3   0 10 20 70 80 80
0 1 2 3 4 5   0 0 0 2 2 3   0 10 20 70 80 80
0 1 2 3 4 5   0 0 0 2 2 3   0 10 20 70 80 80

Observe como os valores em cada coluna de dist[] e de pa[] mudam de uma iteração para a seguinte.  A CPT calculada pelo algoritmo tem arcos  0-1 0-2 2-3 2-4 3-5.

Exemplo D.  Voltamos a examinar o exemplo B. Veja novamente a lista de arcos e seus custos:

0-2 0-3 0-4 2-4 3-4 3-5 4-1 4-5 5-1 1-2
 70  50  30  10  10  20   0  30  50  30

Aplique o algoritmo de Dijkstra a partir da raiz 0. Veja o estado dos vetores pa[] e dist[] no início de sucessivas iterações (com a cor vermelha indicando vértices maduros:

T             pa[]          dist[]
                                  
0             0 - - - - -   0  *  *  *  *  *
0 2 3 4       0 - 0 0 0 -   0  * 70 50 30  *
0 2 3 4 1 5   0 4 0 0 0 4   0 30 70 50 30 60
0 2 3 4 1 5   0 4 1 0 0 4   0 30 60 50 30 60
0 2 3 4 1 5   0 4 1 0 0 4   0 30 60 50 30 60
0 2 3 4 1 5   0 4 1 0 0 4   0 30 60 50 30 60
0 2 3 4 1 5   0 4 1 0 0 4   0 30 60 50 30 60

A CPT calculada pelo algoritmo tem arcos  0-3 0-4 4-1 4-5 1-2.

Análise do algoritmo

Para provar que o algoritmo de Dijkstra está correto, é preciso verificar que as seguintes propriedades invariantes valem no início de cada iteração:

1. pa[] representa uma árvore radicada T, que tem raiz s;
2. todos os arcos de T são justos  e  dist[x] < ∞ se e somente se x pertence a T ;
3. para todo vértice maduro v, todo arco v-w de G está relaxado em relação a dist[].

Verificados os invariantes, considere o início da última iteração. Nesse momento, todos os vértices de T estão maduros. Logo, pelo invariante iii, todo arco de G com ponta inicial em T está relaxado em relação a dist[]. Em particular, para todo arco v-w de G, se v está em T então dist[w] < ∞ e portanto w está em T, conforme o invariante ii. Segue daí que todo vértice ao alcance de s em G pertence a T. Se supusermos, para simplificar a discussão, que todos vértices de G estão ao alcance de s, podemos concluir que T é geradora de G. Resumindo: em virtude do invariante ii, dist[] é o vetor das distância em T a partir de s e, em virtude do invariante iii, dist[] é um potencial relaxado. Segue daí que T é uma CPT de G com raiz s.

Se nem todos os vértices estiverem ao alcance de s, o algoritmo produz uma CPT do sub­grafo de G induzido pelos vértices que estão ao alcance de s.

Primeira implementação do algoritmo

A função GRAPHcptD1() abaixo implementa o algoritmo de Dijkstra que discutimos acima.  A função supõe que o grafo G é representado por listas de adjacência com custos e portanto, para cada vértice v e cada a em G->adj[v], o arco que vai de v a a->w tem custo  a->c.  O conjunto dos vértices maduros é representado por seu vetor característico mature[].  O infinito é representado pela constante INT_MAX. A função supõe, tacitamente, que o valor da expressão dist[v] + a->c é sempre menor que INT_MAX. (Para garantir isso, basta que a soma de todos os custos seja menor que INT_MAX. Essa condição também garantirá que não teremos overflow aritmético.)

/* Esta função recebe um grafo G com custos 
   positivos nos arcos 
   e um vértice s.
   Calcula e armazena em pa[0..V-1] o vetor de pais
   de uma CPT de G com raiz s
   (supondo que todos os vértices de G 
   estão ao alcance de s).
   As distâncias a partir de s são armazenadas
   no vetor dist[].

   (A função implementa o algoritmo de Dijkstra.

   O código foi inspirado no
   Programa 20.3 de Sedgewick.) */

void GRAPHcptD1( Graph G, vertex s,
                 vertex *pa, int *dist)
{
   bool mature[1000];
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, mature[v] = false, dist[v] = INT_MAX;
   pa[s] = s, dist[s] = 0;

   while (true) {
      // escolha de y:
      int min = INT_MAX;
      vertex y;
      for (vertex z = 0; z < G->V; ++z) {
         if (mature[z]) continue;
         if (dist[z] < min) 
            min = dist[z], y = z;
      }
      if (min == INT_MAX) break;
      // atualização de dist[] e pa[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         if (mature[a->w]) continue;
         if (dist[y] + a->c < dist[a->w]) {
            dist[a->w] = dist[y] + a->c;
            pa[a->w] = y;
         }
      }
      mature[y] = true;
   }
}

A função supõe que todos os vértices do grafo estão ao alcance de s. Mas mesmo que essa condição não esteja satisfeita, o resultado da função é útil, pois a árvore definida por pa[] é uma CPT do sugrafo induzido pelos vértices que estão ao alcance de s.

Desempenho.  A função GRAPHcptD1() examina cada arco do grafo uma única vez.  Quando aplicada a um grafo com V vértices e A arcos, a função consome tempo proporcional a V² + A no pior caso.  Como A < V², o consumo de tempo da função é proporcional a

V²

no pior caso. Podemos dizer que a função é linear quando aplicada a grafos densos, uma vez que o tamanho de tais grafos é proporcional a V².

Segunda implementação do algoritmo

A primeira implementação do algoritmo de Dijkstra começa cada iteração examinando os vértices imaturos, um por um, à procura de algum que minimize dist[]. Para acelerar esse processo, a implementação que examinaremos a seguir mantém os vértices imaturos em uma fila priorizada de mínimo (= min priority queue).  (Seria suficiente manter na fila priorizada os vértices imaturos que pertencem a T, mas é mais simples colocar na fila todos os vértices imaturos, mesmo os que estão fora de T.)

/* Recebe um grafo G com custos positivos nos arcos 
   e um vértice s.
   Calcula e armazena em pa[] o vetor de pais
   de uma CPT de G com raiz s
   (supondo que todos os vértices de G 
   estão ao alcance de s).
   As distâncias a partir de s são armazenadas
   no vetor dist[].

   (A função implementa o algoritmo de Dijkstra.
   O código foi inspirado no
   Programa 21.1 de Sedgewick.) */

void GRAPHcptD2( Graph G, vertex s,
                 vertex *pa, int *dist)
{
   bool mature[1000];
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, mature[v] = false, dist[v] = INT_MAX;
   pa[s] = s, dist[s] = 0;
   PQinit( G->V);
   for (vertex v = 0; v < G->V; ++v)
      PQinsert( v, dist);

   while (!PQempty( )) {
      vertex y = PQdelmin( dist);
      if (dist[y] == INT_MAX) break;
      // atualização de dist[] e pa[]:
      for (link a = G->adj[y]; a != NULL; a = a->next) {
         if (mature[a->w]) continue;
         if (dist[y] + a->c < dist[a->w]) {
            dist[a->w] = dist[y] + a->c;
            PQdec( a->w, dist);
            pa[a->w] = y;
         }
      }
      mature[y] = true;
   }
   PQfree( );
}

Os vértices imaturos ficam todos armazenados numa fila priorizada de mínimo. As prioridades dos vértices são dadas por dist[].  A fila é manipulada pelas seguintes funções:

• PQinit(G->V):  inicializa uma fila priorizada com capacidade para G->V vértices.
• PQempty():  decide se a fila está vazia.
• PQdelmin(dist):  retira da fila um vértice v que minimiza dist[].
• PQinsert(v,dist):  insere v na fila com prioridade dist[v].
• PQdec(v,dist):  reorganiza a fila depois que o valor de dist[v] diminuiu.

A maneira usual de implementar a fila priorizada usa uma estrutura de heap.

Tal como na primira implementação, se nem todos os vértices estiverem ao alcance de s, o vetor pa[] produzido pela função representará uma CPT do sugrafo de induzido pelos vértices que estão ao alcance de s.

Desempenho.  Suponha que nosso grafo tem V vértices e A arcos.  Se a fila priorizada for implementada em um heap, todas as operações sobre a fila serão executadas em tempo limitado por log V.  Nesse caso, GRAPHcptD2() consumirá tempo proporcional a (V+A) log V  no pior caso.  Se A ≥ V − 1, como acontece em muitas aplicações, o consumo de tempo será proporcional a

A log V

no pior caso.  Podemos dizer que GRAPHcptD2() é linearítmica.

A função GRAPHcptD2() é mais sofisticada que GRAPHcptD1(), pois usa uma fila priorizada. Apesar disso, ela é assintoticamente mais lenta que GRAPHcptD1() quando A é próximo de V².

Como se compara o consumo de tempo de GRAPHcptD2() com o de GRAPHcptD1()?  Se nos restringirmos a grafos esparsos, GRAPHcptD2() é assintoticamente mais rápida que GRAPHcptD1(). Se nos restringirmos a grafos densos, a relação se inverte: GRAPHcptD1() é assintoticamente mais rápida que GRAPHcptD2().