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

Problema:  Dado um vértice s de um grafo com custos positivos nos arcos, encontrar uma árvore de caminhos baratos com raiz s no grafo.

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.

Sumário:

iou-graph-10-nodes-and-20-edges.png

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] + cxy,
  2. acrescente o arco x-y e o vértice yT  e
  3. faça dist[y] = dist[x] + cxy.

Nessa descrição,  cxy  é 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
figs/mine/diwheel6-j02-invert21.png

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

Exercícios 1

  1. Para que serve o algoritmo de Dijkstra?  Que problema resolve?
  2. Aplique o algoritmo de Dijkstra, com vértice inicial 0, ao seguinte grafo com custos nos arcos:
    0-1 1-2 2-3 3-4 4-5 0-2 0-5
      1   1   1   1   1   3   6
    
  3. ★ Considere o grafo com custos nos arcos descrito abaixo.  Seja T a árvore radicada cujos arcos são  0-1 1-2 1-3 .  Faça uma lista de todos os arcos da franja de T. Para cada arco v-w da franja, anote o valor da expressão dist[v]+cvw e destaque os arcos que minimizam a expressão.
    0-1 0-5 1-2 1-3 2-3 2-5 2-6 3-6 5-1 5-4 5-6 6-3 6-4
     10  65  10  20  10  40  50  50  10   0   5  20  20
    
  4. Implementação ingênua.  Escreva uma função GRAPHcptD0() que implemente o algoritmo de Dijkstra de maneira ingênua. Sua implementação deve seguir de perto a descrição do algoritmo dada acima.  Mostre que sua função consome VA unidades de tempo no pior caso, sendo V o número de vértices e A o número de arcos do grafo.
  5. ★ Compare o algoritmo de Dijkstra com o algoritmo de Prim para o problema da MST (árvore geradora mínima). Quais as semelhanças? Quais as diferenças? Comece por apontar as diferenças entre os problemas que os dois algoritmos resolvem.

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]+cdist[z], e está justo se dist[y]+cdist[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.

figs/mine/diwheel6-j02-invert21.png

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.

Exercícios 2

  1. Mostre que nossa primeira descrição do algoritmo de Dijkstra é equivalente à segunda.
  2. No contexto do algoritmo de Dijkstra, denote por H o grafo que consiste em T mais todos os arcos de G que vão de um vértice maduro a um vértice imaturo.  (Note que H não é, em geral, o sub­grafo de G induzido pelos vértices de T.)  Prove diretamente a partir da descrição do algoritmo que, no início de cada iteração, para cada vértice w de H, dist[w] é a distância correta de sw no grafo H.
  3. ★ Considere o grafo com custos nos arcos definido a seguir. Uma certa iteração do algoritmo de Dijkstra começa com a árvore radicada cujos arcos são 6-1, 6-2, 1-0, 1-41-5, estando maduros os vértices 61. Mostre a árvore radicada e o conjunto de vértices maduros no início da próxima iteração.
    6-1 6-2 1-2 4-3 5-3 0-3 1-4 2-4 0-4 1-5 6-0 1-0 2-0
     15  16  25  25  15  15  44  42  11  45  47  30  30
    
  4. ★ Considere o grafo com custos nos arcos descrito abaixo.  Suponha que uma iteração do algoritmo de Dijkstra começa com a árvore radicada cujos arcos são  0-1 0-5 1-2 1-3  e com o conjunto  0 1  de vértices maduros.  Quais os valores das variáveis T e dist[] no início da próxima iteração? Qual o estado do vetor dist[] no início da próxima iteração?
    0-1 0-5 1-2 1-3 2-3 2-5 2-6 3-6 5-1 5-4 5-6 6-3 6-4
     10  65  10  20  10  40  50  50  10   0   5  20  20
    
  5. Considere o grafo com custos nos arcos descrito abaixo. Use o algoritmo de Dijkstra para encontrar uma CPT com raiz 1. Faça o rastreamento da execução da função.
    0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2
     10  30  10  10  60  50  10  40  20
    

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.

Exercícios 3

  1. Prova dos invariantes.  Prove os invariantes do algoritmo de Dijkstra.  Para fazer isso, será necessário introduzir dois invariantes auxiliares:  (iv) para todo vértice maduro v e todo vértice imaturo z tem-se dist[v]dist[z]  e  (v) todo vértice imaturo de T é uma folha.  [Solução]
  2. Mostre que, no início de cada iteração do algoritmo de Dijkstra, o potencial dist[] é uma numeração topológica da árvore representada por pa[].  (Use os invariantes do algoritmo.)
  3. Arcos negativos. Mostre que o algoritmo de Dijkstra pode produzir resultados errados se o grafo tiver arcos de custo negativo, mesmo que não tenho ciclo negativo.  [Solução]

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 V2 + A no pior caso.  Como A < V2, o consumo de tempo da função é proporcional a

V2

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

Exercícios 4

  1. ★ Como começa cada iteração na função GRAPHcptD1()?  Quais as informações disponíveis no início da iteração?
  2. Verifique que a função GRAPHcptD1() implementa corretamente o algoritmo de Dijkstra.
  3. Instâncias extremas.  A aplicação da função GRAPHcptD1() a um grafo que tem apenas um vértice produz o resultado correto?  E a aplicação a um grafo com apenas 2 vértices?  E a aplicação a um grafo que consiste em um caminho apenas?  Justique suas respostas diretamente a partir do código da função.
  4. Desempenho.  Prove que GRAPHcptD1() consome tempo proporcional a V2 + A no pior caso.
  5. ★ Escreva uma variante da função GRAPHcptD1() que receba dois vértices s e t e devolva a distância de st. Escreva código enxuto, sem variáveis e operações supérfluas.
  6. Considere o grafo com custos nos arcos definido abaixo. Submeta o grafo à função GRAPHcptD1(). Suponha que no início de uma certa iteração a árvore radicada tem arcos 0-1, 1-2, 1-3 e 1-4 e os únicos vértices maduros são 01.  Qual o estado dos vetores pa[] e dist[] no início dessa iteração?  Qual o estado desses vetores e o conjunto de vértices maduros no início da próxima iteração?
    0-1 0-2 1-2 1-3 1-4 2-3 2-4 3-4 3-5 4-5 4-0
     10  40  20  50  60  20  50  10  20   0   0
    
  7. Considere o grafo com custos nos arcos definido a seguir. Uma certa iteração da função GRAPHcptD1() começa com a árvore radicada cujos arcos são 6-1, 6-2, 1-0, 1-41-5, estando maduros apenas os vértices 61. Qual o estado dos vetores pa[] e dist[] no início dessa iteração?  Qual o estado desses vetores e o conjunto de vértices maduros no início da próxima iteração?
    6-1 6-2 1-2 4-3 5-3 0-3 1-4 2-4 0-4 1-5 6-0 1-0 2-0
     15  16  25  25  15  15  44  42  11  45  47  30  30
    
  8. Aplique a função GRAPHcptD1() com parâmetro s igual a 0 ao grafo com custos nos arcos definido pela tabela a seguir.
    0-2 0-3 0-4 2-4 3-4 3-5 4-1 4-5 5-1 1-2
     70  20  40  10  10  30  40  10  20   0
    
  9. Considere o grafo com custos nos arcos a seguir. (O comprimento geométrico de cada arco na figura é proporcional ao custo do arco.)  Verifique que a figura representa uma CPT com raiz 5.
    0-2 0-4 1-3 2-7 3-6 4-5 4-7 5-1 5-4 5-7 6-0 6-2 6-4 7-3 7-5
     26  38  29  34  52  35  37  32  36  27  58  40  93  39  28
    
  10. [Sedgewick 21.17]  Considere o grafo não-dirigido cujos vértices são os pontos no plano que têm as coordenadas a seguir.
      0     1     2     3     4     5
    (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 à função GRAPHcptD1() com s = 0.  Exiba o estado dos vetores pa[] e dist[] no início de cada iteração.

  11. Escreva uma versão de GRAPHcptD1() que imprima um rastreamento da execução da função. Imite o estilo dos exemplos acima.
  12. Escreva uma variante da função GRAPHcptD1() para grafos representados por matriz de adjacências.
  13. Compare o código da função GRAPHcptD1() com o da função UGRAPHmstP1(), que calcula uma MST.  Quais as semelhanças? Quais as diferenças?

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:

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 AV − 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 V2.

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

Exercícios 5

  1. Mostre que a função GRAPHcptD2() é uma implementação correta do algoritmo de Dijkstra.
  2. Como começa uma iteração genérica da função GRAPHcptD2()?  Que informações estão disponíveis no início da iteração?
  3. Instâncias extremas.  A aplicação da função GRAPHcptD2() a um grafo que tem apenas um vértice produz o resultado correto?  E a aplicação a um grafo com apenas dois vértices?  E a aplicação a um grafo que consiste em um caminho apenas?  Justique suas respostas diretamente a partir do código da função.
  4. Desempenho.  Prove que GRAPHcptD2() consome tempo proporcional a (V+A) log V no pior caso se a fila priorizada for implementada em um heap.
  5. Escreva uma versão all-in-one de GRAPHcptD2(). A versão deve incorporar os códigos das funções que manipulam a fila priorizada.
  6. ★ Escreva uma variante da função GRAPHcptD2() que receba dois vértices s e t e devolva a distância — apenas a distância — de st. Escreva código enxuto, sem variáveis e operações supérfluas.
  7. Escreva uma variante da função GRAPHcptD2() para grafos representados por matriz de adjacências.
  8. Compare o código de GRAPHcptD2() com o de UGRAPHmstP2(), que calcula uma MST.  Quais as semelhanças? Quais as diferenças?

Exercícios 6

  1. Terceira implementação.  Escreva uma variante GRAPHcptD3() da função GRAPHcptD2() em que a fila priorizada armazena apenas os vértices imaturos que pertencem a T.
  2. Atualize suas bibliotecas.  Acrescente as implementações do algoritmo de Dijkstra discutidas neste capítulo à biblioteca GRAPHlists.  Também acrescente versões apropriadas das funções à biblioteca GRAPHmatrix.  Atualize os correspondentes arquivos-interface.
  3. [Sedgewick 21.20]  O diâmetro de um grafo não-dirigido com custos nas arestas é o máximo das distâncias entre dois vértices. Escreva código que use alguma das implementações do algoritmo de Dijkstra para calcular o diâmetro de um grafo não-dirigido com custos positivos nas arestas.
  4. [Sedgewick 21.8]  Escreva um programa que escolha V pontos aleatórios no plano e construa um grafo não-dirigido que tem esses pontos por vértices. Dois vértices v e w são adjacentes se a distância geométrica entre v e w no plano é no máximo d.  (Veja exercício no capítulo Grafos não-dirigidos aleatórios.)  O custo de cada arco v-w é a distância geométrica entre vw. Depois de construir o grafo, o seu programa deve calcular a distância do primeiro vértice gerado a cada um dos outros.
  5. [Sedgewick 21.28]  Escreva uma função que receba conjuntos S e T de vértices de um grafo com custos positivos nos arcos e calcule a distância de ST, ou seja, o custo de um caminho mínimo dentre os que começam em S e terminam em T. (Basta introduzir uma pequena modificação no algoritmo de Dijkstra.) 
  6. [Sedgewick 21.26]  Escreva um algoritmo que encontre um arco cuja remoção causaria o maior aumento na distância de um dado vértice s a um dado vértice t.
  7. Minimizando mudanças de direção em uma subgrade.  Seja G um sub­grafo não-dirigido de uma grade não-dirigida. Cada vértice é vizinho de no máximo quatro outros: um ao norte (N), um a leste (L), um ao sul (S) e um a oeste (O). Sejam s e t dois vértices de G e seja f uma direção inicial N, L, S, ou O. Problema: encontrar um caminho de s a t que começe na direção f e minimize o número de mudanças de direção.  (Sugestão: Reduza ao problema do caminho de custo mínimo. Troque cada vértice v por 4 novos vértices: vN, vL, vS, vO, cada um representando uma possível direção de chegada a v. Acrescente arestas apropriadas e atribua custos 0 e 1 às arestas conforme haja mudança de direção ou não.)
  8. Bottleneck: caminhos maxmin.  Suponha dado um grafo com custos positivos nos arcos. O gargalo de um caminho é o custo do seu arco mais barato (ou melhor, o custo um arco de custo mínimo do caminho). Considere o problema de encontar um caminho de gargalo máximo dentre todos os caminhos que levam de um vértice s a um vértice t.  (Sugestão: Uma adaptação apropriada do algoritmo de Dijkstra resolve o problema.)
  9. [Sedgewick 21.30]  Caminho minmax.  Suponha dado um grafo com custos positivos nos arcos. O gargalo (antigargalo?) de um caminho é o custo do seu arco mais caro (ou melhor, o custo um arco de custo máximo do caminho).  Adapte o algoritmo de Dijkstra para encontrar um caminho de gargalo mínimo de um vértice s a um vértice t.
  10. Escreva uma função que encontre um caminho mínimo num tabuleiro com n linhas e n colunas. Cada casa do tabuleiro tem um custo positivo e o custo de um caminho é a soma dos custos das casas por onde o caminho passa. O seu caminho deve começar na casa que está no cruzamento da linha 1 com a 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 na vertical (não na diagonal).
  11. [Sedgewick 21.52] Custos nos vértices.  Suponha dado um grafo com custos positivos nos vértices (não nos arcos). O custo de um caminho num tal grafo é a soma dos custos dos vértices do caminho. Quero encontrar um caminho mínimo dentre os que começam num vértice s e terminam num vértice t.  (Veja exercício Custos nos vértices no capítulo Distâncias e potenciais sob custos positivos.)  Modifique o algoritmo de Dijkstra para resolver o problema.
  12. É possível usar o algoritmo para árvore geradora de custo mínimo (como o de Prim ou o de Kruskal), sem alterações, para encontrar uma árvore geradora de custo máximo num grafo não-dirigido conexo com custos nas arestas?  É possível usar um algoritmo para caminhos mínimos (como o de Dijkstra, por exemplo) para encontrar um caminho de custo máximo de um dado vértice s a um dado vértice t?
  13. Caminhos simples de custo máximo?  Digamos que a antidistância de um vértice s a um vértice t num grafo com custos poitivos nos arcos é o custo de um caminho simples de custo máximo dentre os que vão de st. Denote por ad[] o vetor de antidistâncias a partir de s. Modifique o algoritmo de Dijkstra da seguinte maneira: em cada iteração, escolha um arco x-y na franja de T que maximize a soma ad[x] + cxy. É verdade que essa versão modificada calcula a antidistância de um vértice s e cada um dos demais vértices do grafo?
  14. Todos os pares.  Escreva uma função que receba um grafo com custos positivos nos arcos e preencha uma matriz dist[0..V-1][0..V-1] com as distância entre todos os pares de vértices.  (Imagine uma tabela de distância rodoviárias entre as cidades de um país.)