Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Algoritmo de Dijkstra

"Computer science is no more about computers
than astronomy is about telescopes."

— Edsger W. Dijkstra

Esta página discute um algoritmo eficiente para o Problema da SPT:

Dado um digrafo com custos não negativos nos arcos e um vértice s, encontrar uma SPT com raiz s no digrafo.

(Observe que os custos são não negativos.)  O algoritmo foi inventado por Dijkstra [pronuncie algo entre "Dêcstra" e "Dêicstra"] e publicado em 1959.  O algoritmo pode ser usado, em particular, para encontrar um caminho de custo mínimo de um dado vértice a outro.

(Esta página é um resumo das seções 21.1 (Underlying Principles) e 21.2 (Dijkstra's Algorithm), p.273-290 do livro de Sedgewick.)

O algoritmo

A estrutura do algoritmo de Dijkstra é muito parecida com a do algoritmo de Prim.  (Embora o algoritmo de Dijkstra, ao contrário do algoritmo de Prim, só se aplique a custos não negativos.)

No início de cada iteração, temos uma arborescência T com raiz s.  Para qualquer vértice w fora de T, o custo de w em relação a T é, por definição,

a distância de  s  a  w  no digrafo  T+F,

sendo  F  a franja de T.  Aqui, a franja de T é o conjunto de todos os arcos que saem de T.  Em outras palavras, o custo de um vértice w que está fora de T é o custo de um caminho mínimo dentre os que começam em s, terminam em w, e só têm um arco — o último — fora de T.  Diremos que o último arco de um tal caminho mínimo é o arco-pai de w. 

Cada iteração do algoritmo de Dijkstra consiste no seguinte:

• se  a franja de T não é vazia
  • então  seja  w  um vértice fora de T que tem custo mínimo
  • então  seja  e  o arco-pai de w
  • então  comece nova iteração com  T+e  no papel de T
  • senão  pare

Nas implementações abaixo, a arborescência T será representada por um vetor parent.  O custo de cada vértice w será armazenado em  cost[w]  e a ponta inicial do arco-pai de w será armazenada em  frj[w].

Exercícios

1. Prove que o algoritmo de Dijkstra de fato produz uma SPT com origem s.
2. Aplique o algoritmo de Dijkstra ao digrafo abaixo começando com o vértice 1.  No começo de cada iteração, dê o custo de cada vértice.  No fim da última iteração, exiba a SPT com origem 1.

             arco  0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2 
            custo   1   3   1   1   6   5   1   4   2         
   

Implementação para digrafos densos

Suponha que nosso digrafo está representado por sua matriz de adjacência. Como de hábito, se v-w não é arco então adj[v][w] vale maxCOST.  Supõe-se que o valor de maxCOST é tão grande que não se confunde com o custo de um caminho simples.

/* Recebe digrafo G com custos não negativos nos arcos e um vértice s. Calcula uma arborescência de caminhos mínimos com raiz s. A arborescência é armazenada no vetor parent. As distâncias em relação a s são armazenadas no vetor cost. */

/* A função supõe que a soma dos custos de todas os arcos é estritamente menor que maxCOST.  Supõe também que o digrafo tem no máximo maxV vértices. (O código abaixo é uma versão modificada do Programa 20.3, p.238, de Sedgewick.) */

void 
DIGRAPHsptD1 (Digraph G, Vertex s, Vertex parent[], double cost[]) { 
   Vertex w, w0, frj[maxV];
   for (w = 0; w < G->V; w++) { 
      parent[w] = -1; 
      cost[w] = G->adj[s][w]; 
      frj[w] = s; 
   }
   parent[s] = s;
   cost[s] = 0.0;
   while (1) {
      double mincost = maxCOST;
      for (w = 0; w < G->V; w++) 
         if (parent[w] == -1 && mincost > cost[w])
               mincost = cost[w0=w]; 
      if (mincost == maxCOST) break;
      parent[w0] = frj[w0];
      for (w = 0; w < G->V; w++) 
         if (cost[w] > cost[w0] + G->adj[w0][w]) {
            cost[w] = cost[w0] + G->adj[w0][w]; 
            frj[w] = w0; 
         }
   }
}

Note que essa implementação é quase idêntica à implementação correspondente do algoritmo de Prim.

(Duas observações técnicas:  1. Observe como a comparação de cost[w] com cost[w0] + G->adj[w0][w] trata corretamente do caso em que w0 e w não são adjacentes e portanto G->adj[w0][w] vale maxCOST.  2. Estamos supondo, implicitamente, que maxCOST é menor que a metade de DBL_MAX, de modo que a expressão  cost[w0] + G->adj[w0][w] não produz overflow.)

No começo de cada iteração temos uma arborescência com raiz s, representada pelo vetor parent.  No início de cada iteração, as seguinte propriedades valem para cada vértice v:

1. se v está na arborescência então cost[v] é a distância de s a v,
   senão, cost[v] é o custo do vértice v em relação à arborescência;
2. se v está fora da arborescência e cost[v] < maxCOST então
   frj[v] é o penúltimo vértice de um caminho simples de custo cost[v] que liga s a v.

A operação mais característica do algoritmo de Dijkstra é a relaxação de um arco:

         if (cost[w] > cost[w0] + G->adj[w0][w]) {
             cost[w] = cost[w0] + G->adj[w0][w]; 
         }

Essa operação aparece em toda implementação do algoritmo.

Exercícios

3. Considere o grafo cujos vértices são pontos no plano:

              vértice    0     1     2     3     4     5
          coordenadas  (1,3) (2,1) (6,5) (3,4) (3,7) (5,3)
   

   Suponha que as arestas do grafo são

   1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3
   

   e o custo de cada aresta é igual ao comprimento do segmento de reta que liga as pontas da aresta.  Submeta o grafo ao algoritmo de Dijkstra com origem s = 0.  Exiba o estado dos vetores parent e cost no início de cada iteração.

4. Escreva uma variante do algoritmo de Dijkstra que receba dois vértices s e t e devolva a distância de s a t. Escreva código simples, sem variáveis e operações supérfluas.
5. [Desempenho]  Qual o consumo tempo da função DIGRAPHsptD1 no pior caso?
6. Analise e discuta a seguinte variante de DIGRAPHsptD1:

      void DIGRAPHsptD1 (Digraph G, Vertex s, Vertex parent[], double cost[]) { 
         Vertex w, w0, frj[maxV];
         for (w = 0; w < G->V; w++) { 
            parent[w] = -1; 
            cost[w] = maxCOST; 
         }
         frj[s] = s;
         cost[s] = 0.0;
         while (1) {
            double mincost = maxCOST;
            for (w = 0; w < G->V; w++) {
               if (parent[w] == -1 && mincost > cost[w])
                     mincost = cost[w0=w]; 
            if (mincost == maxCOST) break;
            parent[w0] = frj[w0];
            for (w = 0; w < G->V; w++) 
               if (cost[w] > cost[w0] + G->adj[w0][w]) {
                  cost[w] = cost[w0] + G->adj[w0][w]; 
                  frj[w] = w0; 
               }
         }
      }
   

7. Mostre que o algoritmo de Dijkstra pode produzir resultados errados se o digrafo tiver arcos de custo negativo.
8. Digamos que a "antidistância" de um vértice s a um vértice t é o custo de um caminho simples de custo máximo dentre os que vão de s a t. O código abaixo introduz alterações óbvias no algoritmo de Dijkstra para que ele passe a calcular "antidistância" de um vértice s e cada um dos demais vértices do digrafo.  Essa versão modificada produz os resultados esperados em qualquer digrafo com custos não negativos nos arcos?

      void MaxDijkstra(Digraph G, Vertex s, Vertex parent[], double cost[]) { 
         Vertex v, w;
         int parent[maxV]
         for (v = 0; v < G->V; v++) { 
            parent[v] = -1; 
            cost[v] = -1.0;
         }
         frj[s] = s;
         cost[s] = 0.0;
         while (1) {
            Vertex max;
            double maxcost = -1.0;
            for (w = 0; w < G->V; w++) {
               if (parent[w] == -1 && maxcost < cost[w])
                  maxcost = cost[max = w]; 
            if (maxcost == -1.0) break;
            parent[max] = 0;
            for (w = 0; w < G->V; w++) 
               if (parent[w] == -1)
                  if (cost[w] < cost[max] + G->adj[max][w]) 
                     cost[w] = cost[max] + G->adj[max][w]; 
         }
      }
   

Implementação para digrafos esparsos

A implementação para digrafos representados por vetor de listas de adjacência usa uma fila de prioridades, tal como a correspondente implementação do algoritmo de Prim.

/* Recebe digrafo G com custos não negativos nos arcos e um vértice s. Calcula uma SPT com origem s. A SPT é armazenada no vetor parent. As distâncias em relação a s são armazenadas no vetor cost. */

/* A implementação supõe que a soma dos custos de todos os arcos é estritamente menor que maxCOST.  Supõe também que o digrafo tem no máximo maxV vértices.  (O código abaixo é uma versão modificada dos Programas 20.4, p.242, e 21.1, p.284, de Sedgewick.) */

void 
DIGRAPHsptD2 (Digraph G, Vertex s, Vertex parent[], double cost[]) { 
   link p; Vertex w, w0, frj[maxV];
   PQinit(); 
   for (w = 0; w < G->V; w++) 
      parent[w] = frj[w] = -1; 
   parent[s] = s;
   cost[s] = 0.0; 
   for (p = G->adj[s]; p != NULL; p = p->next) {
      cost[p->w] = p->cost; 
      PQinsert(p->w); 
      frj[p->w] = s; 
   } 
   while (!PQempty()) {
      w0 = PQdelmin(); 
      parent[w0] = frj[w0]; 
      for (p = G->adj[w0]; p != NULL; p = p->next) {
         w = p->w;
         if (frj[w] == -1) { 
            cost[w] = cost[w0] + p->cost; 
            PQinsert(w); 
            frj[w] = w0; 
         } 
         else if (cost[w] > cost[w0] + p->cost) {
            cost[w] = cost[w0] + p->cost; 
            PQdec(w); 
            frj[w] = w0; 
         }
      }
   }
}

(Note a operação de relaxação  if (cost[w] > cost[w0]+p->cost) { cost[w] = cost[w0]+p->cost; }  característica do algoritmo de Dijkstra.)

A função DIGRAPHsptD2 usa uma fila de vértices com prioridades definidas pelo vetor cost.  A fila é manipulada pelas seguintes funções:

• PQinit():  inicializa uma fila de vértices em que todo vértice v tem prioridade cost[v].
• PQempty():  devolve 1 se a fila estiver vazia e 0 em caso contrário.
• PQinsert(v):  insere o vértice v na fila.
• PQdelmin():  retira da fila um vértice de prioridade mínima.
• PQdec(v):  reorganiza a fila depois que o valor de cost[v] foi decrementado.

A implementação clássica da fila de prioridades usa uma estrutura de heap.

Exercícios

9. [Desempenho]  Qual o consumo tempo da função DIGRAPHsptD2 no pior caso?  Suponha que a fila de prioridades é implementada em um heap.

Outra implementação para digrafos esparsos

Tal como fizemos com o algoritmo de Prim, podemos organizar a implementação do algoritmo de Dijkstra de maneira um pouco diferente, inserindo todos os vértices na fila de prioridades antes mesmo do início do processo iterativo:

/* (Código inspirado no Programa 21.1, p.284, de Sedgewick.) */

void 
DIGRAPHsptD3 (Digraph G, Vertex s, Vertex parent[], double cost[]) { 
   Vertex w, w0; link p;
   for (w = 0; w < G->V; w++) { 
      parent[w] = -1;
      cost[w] = maxCOST; 
   }
   parent[s] = s;
   cost[s] = 0.0; 
   for (p = G->adj[s]; p != NULL; p = p->next)
      cost[p->w] = p->cost; 
   PQinit(); 
   for (w = 0; w < G->V; w++)
      if (w != s) PQinsert(w); 
   while (!PQempty()) {
      w0 = PQdelmin();
      if (cost[w0] == maxCOST) break;
      for (p = G->adj[w0]; p != NULL; p = p->next) {
         w = p->w;
         if (cost[w] > cost[w0] + p->cost) { 
            cost[w] = cost[w0] + p->cost; 
            PQdec(w); 
            parent[w] = w0; 
         }
      }
   }
}

Exercícios

10. No código da função DIGRAPHsptD3, não deveríamos fazer  "if (cost[w] > cost[w0] + p->cost) { }"  somente se w está na fila?

Mais exercícios

11. O diâmetro de um grafo é o máximo das distâncias entre dois vértices. Escreva código que usa o algoritmo de Dijkstra para calcular o diâmetro de um grafo.
12. Escreva um algoritmo que encontre um arco cuja remoção causa o maior aumento na distância de um vértice s a um vértice t.
13. Escreva uma função que faça a análise de sensibilidade em relação a um par (s,t) de vértices.  Sua função deve preencher uma matriz M indexada pelos vértices de tal modo que M[v][w] valha 1 se v-w é um arco cujo custo pode ser aumentado sem que isso aumente a distância de s a t. Nos demais casos, M[v][w] deve valer 0.
14. Escreva uma função que receba conjuntos S e T de vértices e calcule a distância de S a T.  (Basta introduzir uma pequena modificação no algoritmo de Dijkstra.) 
15. Escreva um programa que gere V pontos aleatórios no plano e construa um grafo que tem esses pontos por vértices. Dois vértices v e w são adjacentes se a distância euclidiana entre v e w é no máximo d.  (Veja o exercício 17.73.)  O custo de cada arco v-w é a distância euclidiana entre v e w. Depois de gerar o digrafo, o seu programa deve calcular a distância do primeiro vértice gerado a todos os demais.
16. [Todos os pares]  Escreva uma função que receba um digrafo G com custos não negativos nos arcos e preencha uma matriz d[0..V-1][0..V-1] com as distância entre todos os pares de vértices:  d[v][w] deve ser a distância de v a w.
17. Suponha dado um digrafo com custos não negativos associados aos vértices (e não aos arcos). O custo de um caminho num tal digrafo é a soma dos custos dos vértices do caminho. Quero encontrar um caminho de custo mínimo dentre os que começam num vértice s e terminam num vértice t.  Adapte o algoritmo de Dijkstra para resolver esse problema.
18. Escreva uma função que encontre um caminho de custo mínimo num tabuleiro com n linhas e n colunas. Cada casa do tabuleiro tem um custo não negativo. O seu caminho deve começar na casa que está no cruzamento da linha 1 com coluna 1 e terminar na casa que está no cruzamento da linha n com a coluna n. O caminho só pode passar de um casa para a casa vizinha na horizontal ou vertical (não na diagonal). O custo de um caminho é a soma dos custos dos casas por onde o caminho passa.