Página 470

24.2-3 A formulação de diagramas PERT dada anteriormente é um tanto antinatural. Seria mais natural que os vértices representassem serviços e arestas, restrições de seqüenciamento; isto é, a aresta (u, v) indicaria que o serviço u deve ser executado antes do serviço v. Então, seriam atribuídos pesos a vértices, não a arestas. Modifique o procedimento DAG-SHORTEST-PATHS de forma que ele encontre um caminho mais longo em um grafo acíclico orientado com vértices ponderados em tempo linear.

Solução (apresentada pelo aluno Guilherme Torres)

O problema trata vértices como serviços e arestas como restrições de sequenciamento, sendo que cada serviço tem o seu peso. Para a solução do problema, as modificações aconteceram em dois métodos: INITIALIZE-SINGLE-SOURCE, que inicializava a estimativa de caminho mais curto (d[v]) de todos os vértices com o valor infinito, exceto o vértice inicial, que recebia zero; e RELAX, que realizava o relaxamento de uma aresta (u,v), isto é, se o caminho passando pela aresta (u, v) fosse mais curto que o d[v] atual, o valor de d[v] seria atualizado. O procedimento DAG-SHORTEST-PATHS não sofreu nenhuma alteração.

Para o novo problema, o conceito de d[v] é alterado. Originalmente, d[v] consistia da soma do peso de todas as arestas do caminho do vértice inicial ao vértice v. Neste problema, como o peso não está mais nas arestas, d[v] consistirá do peso de todos os vértices pertencentes ao caminho do vértice inicial a v, excluindo-se o peso de v. Assim, ao relaxar uma aresta (u, v) , o procedimento RELAX compara o valor atual de d[v] com d[u] + w[u] (peso do caminho até o vértice u + peso do vértice u).

Além da mudança descrita acima, o relaxamento será inverso neste caso: caso o tamanho do caminho passando pela aresta que está sendo examinada seja maior que o valor atual, d[v] receberá o valor deste novo caminho. No procedimento INITIALIZE-SINGLE-SOURCE, a mudança será a inicialização das estimativas de caminhos de cada vértice com o valor (- infinito). O vértice inicial continua sendo inicializado com zero.

Informalmente, a solução executará as seguintes etapas: primeiramente, os vértices serão ordenados topologicamente*. O segundo passo será sua inicialização, como descrita acima. Por último, cada vértice, tomado em seqüência topologicamente ordenada, terá suas arestas adjacentes relaxadas. Os algoritmos modificados são apresentados a seguir.

INICIALIZE-SINGLE-SOURCE-NEG (G, s)
1      for cada vértice v pertencente a V[G] do
2           d[v] <- (- infinito)
3           PI[v] <- NIL
4      d[s] <- 0

RELAX-LONG (u, v, w)
1      if d[v] < d[u] + w[u] then
2           d[v] <- d[u] + w[u]
3           PI[v] <- u

DAG-LONGEST-PATHS (G, w, s)
1      ordenar topologicamente os vértices de G
2      INICIALIZE-SINGLE-SOURCE-NEG (G, s)
3      for cada vértice u tomado em seqüência topologicamente ordenada do
4            for cada vértice v pertencente a Adj[u] do
5                  RELAX-LONG(u, v, w)

*O procedimento de ordenação topológica pode ser consultado no capítulo 22 do livro texto, p. 436, ou na ata da aula.

Página 475

24.3-6 Seja G = (V, E) um grafo orientado ponderado com função peso w: E -> {0, 1, ..., W} para algum inteiro não negativo W. Modifique o algoritmo de Dijkstra para calcular os caminhos mais curtos a partir de um vértice de origem s dado no tempo O(WV + E).

Solução (apresentada pelo aluno André Santanchè)

Com as novas características, os procedimentos de criação da fila de prioridade, EXTRACT-MIN e DECREASE-KEY são modificados. A modificação base é realizada na fila de prioridades Q, utilizada em DIJKSTRA. Como o tamanho do intervalo é conhecido, a fila será implementada como um array Q de VW + 1 posições (de 0 a VW) . Cada posição desse array será um ponteiro para uma lista duplamente ligada, que conterá os vértices cuja estimativa de caminho mínimo (d[v]) é igual ao índice do array. Isto é, qualquer vértice com estimativa de caminho mínimo d[v] estará na lista da posição Q[d[v]], e os vértices com d[v] = infinito ficarão na posição Q[VW]. Como o peso das arestas é no máximo W, o maior valor de estimativa de caminho mínimo que um vértice pode atingir é (V - 1)W.

O algoritmo funciona como se segue: inicialmente, as estimativas de cada vértice (d[v]) recebem o valor infinito, exceto o nó inicial, que recebe o valor zero. Em seguida, são inseridos no array Q, nas posições correspondentes à seus valores de d[v] (os valores infinitos serão armazenados na posição Q[VW]). Esta ação será realizada pelo procedimento BUILD-MIN-HEAP, que agora aparecerá explicitamente no algorimo. A terceira etapa é o relaxamento sucessivo, iniciando o percurso do array Q a partir da posição Q[0]. Caso a lista de Q[0] contenha vértices, o primeiro da lista é retirado da mesma e tem suas arestas adjacentes relaxadas. Caso haja um vértice v cujo valor d[v] seja alterado, sua posição no array Q também é alterada para a posição Q[d[v]]. Estas ações são realizadas pelo procedimento DECREASE-KEY, que estava implícito no algoritmo do livro, mas será explicitado nesta solução.

Após o relaxamento das arestas adjacentes a um dado vértice, a busca pelo menor valor de d[v] no array Q continua, a partir da última posição visitada. Não é necessário iniciar a busca no começo do vetor a cada extração, já que os valores extraídos por EXTRACT-MIN são crescentes. Este fato é resultado da inexistência de arestas com pesos negativos, assim, a cada extração, os valores das estimativas dos próximos vértices a serem extraídos são maiores ou iguais àqueles que não estão mais em Q (estão no conjunto S). Quando o fim do array for atingido (o procedimento IS-EMPTY é responsável por esse teste), significa que todos os vértices já foram extraídos. Assim, o percurso leva VW + 1 passagens, caracterizando o tempo de execução do algoritmo.

Além da alteração na criação de Q (BUILD-MIN-HEAP), e nos procedimentos EXTRACT-MIN e DECREASE-KEY, os procedimentos RELAX, INITIALIZE-SINGLE-SOURCE, IS-EMPTY e DIJKSTRA permaneceram inalterados. Em RELAX, a chamada a DECREASE-KEY foi apenas explicitada, como aconteceu em DIJKSTRA, cujas chamadas a BUILD-MIN-HEAP (para a criação da fila de prioridade Q) e IS-EMPTY (que testa se Q está vazia) também foram explicitadas no algoritmo. Além dessas alterações, foi necessária a criação de dois novos procedimentos:

- INSERT: insere um vértice v no topo da lista duplamente ligada Q[d[v]], no tempo THETA(1).
- REMOVE: remove um vértice v da lista que ele se encontra. Esse procedimento é chamado por DECREASE-KEY pois, quando o valor de d[v] é alterado, e é necessário trocá-lo de lista. Cada vértice representado na lista de adjacência (estrutura do grafo) possui um ponteiro para a estrutura que o representa no array Q. Assim, a busca pelo "nó" correspondente leva tempo THETA(1). A remoção também demora THETA(1), por tratar-se de uma lista duplamente ligada.

Os algoritmos são apresentados abaixo. Os códigos dos novos procedimentos INSERT e REMOVE serão omitidos.

BUILD-MIN-HEAP (Q)
1      posicao <- 0         // posicao é uma variavel global
2      tamanho[Q] <- |V| * W
3      for cada vertice pertencente a V[G] do
4           if (d[v] = infinito)
5                   d[v] <- tamanho [Q]
6           INSERT (Q, v)

EXTRACT-MIN (Q)
1      while ((posicao <= tamanho[Q]) and (Q[posicao] = nulo))
2           posicao <- posicao + 1
3      if (posicao <= tamanho[Q])
4           u <- primeiro de Q[posicao]
5           REMOVE (Q, u)
6           return u
7      return NIL   

DECREASE-KEY (Q, v, chave)
1      REMOVE(Q, v)
2      d[v] <- chave
3      INSERT (Q, v)

IS-EMPTY (Q)
1      while ((posicao <= tamanho[Q]) and (Q[posicao] = nulo))
2           posicao <- posicao + 1
3      return (posicao > tamanho[Q])

INICIALIZE-SINGLE-SOURCE (G, s)
1      for cada vértice v pertencente a V[G] do
2           d[v] <- infinito
3           PI[v] <- NIL
4      d[s] <- 0

RELAX (u, v, w)
1      if d[v] > d[u] + w(u, v) then
2           DECREASE-KEY (Q, v, d[u] + w(u, v))
3           PI[v] <- u

DJIKSTRA (G, w, s)
1      INITIALIZE-SINGLE- SOURCE (G, s)
2      S <- vazio
3      BUILD-MIN-HEAP(Q, G)          //cada vértice v do grafo G é inserido em Q[d[v]]
4      while !(IS-EMPTY(Q))
5          u <- EXTRACT-MIN (Q)  
6          S <- S U {u}
7          for cada vértice v pertencente a Adj[u]
8                RELAX (u, v, w)

Página 475

24.3-7 Modifique seu algoritmo do Exercício 24.3-7 para ser executado no tempo O((V + E) lg W). (Sugestão: Quantos valores de caminhos mais curtos distintos podem existir em V - S em qualquer instante?)

A primeira etapa da solução foi a observação de uma característica importante: além dos valores extraídos por EXTRACT-MIN serem crescentes, devido à inexistência de arestas com pesos negativos, a diferença entre as estimativas d[v] de quaisquer vértices que ainda estão em Q (exceto os de estimativa infinita) é no máximo W. A prova desta afirmação é apresentada abaixo:

Afirmação: Sejam v₁ e v₂ dois vértices no heap Q. Então d[v₂] <= d[v₁] + W.

Suponha por absurdo que d[v₂] > d[v₁] + W, isto é, que a diferença entre d[v₁] e d[v₂] é maior que W.

Sendo u o predecessor de v₂, temos que u é adjacente a v₂, que u já foi extraído do heap Q, e além disso:

d[v₂] = d[u] + w(u, v₂)

Substituindo na suposição:

d[v₁] + W < d[u] + w(u, v₂)
d[u] - d[v₁] > W - w(u, v₂) >= 0

Como w(u, v₂) <= W:

d[u] - d[v₁] > 0
d[u] > d[v₁]

O que é um absurdo, pois u já foi extraído do heap, enquanto que v₁ainda está lá, e portanto d[u] deve ser necessariamente menor ou igual que d[v₁]. Isto prova que a distância entre dois vértices quaisquer que ainda estejam no heap é no máximo W.

Tendo isto em vista, a solução consiste em acrescentar ao vetor Q um outro heap binário B, onde são colocadas as cabeças não nulas das listas Q[i], com chave i. Como há no máximo W+1 chaves distintas, o heap B nunca terá mais de O(W) elementos e as operações nele demorarão O(log W). O código IS-EMPTY(Q) será substituído por IS-EMPTY(B) e o loop while em EXTRACT-MIN(Q) será substituído por EXTRACT-MIN(B).