1. Exercício 24.3-3 do CLRS3 ou CLRS2. Suponha que mudemos a linha 4 do algoritmo de Dijkstra para o seguinte:
4 \text { while }|Q|>1
Essa mudança faz o laço while ser executado |\mathrm{V}|-1 vezes em lugar de |\mathrm{V}| vezes. Esse algoritmo proposto é correto?

Passo 1

O enunciado pergunta se a seguinte modificação do algoritmo de Dijkstra é correta: substituir a linha 4 original por
4\\ \text{while}\\ |Q|>1
ou seja, fazer o laço while executar |\!V\!|-1 vezes em vez de |\!V\!| vezes.
Informações relevantes dadas:
  • O algoritmo considerado é o de Dijkstra (com pesos de arestas não negativos).
  • Originalmente o laço while iterava enquanto |Q|>0 (extraindo todos os vértices).
  • A proposta faz o laço parar quando resta exatamente um vértice em Q.
    A pergunta é: esse algoritmo proposto (com while \(|Q|>1\)) continua correto (ou seja, ainda calcula as distâncias mínimas \delta(s,v) do vértice fonte s para todo vértice v)?

Passo 2

Vamos lembrar, de forma bem clara e passo a passo, o que o algoritmo faz e quais são os conceitos usados. Não vou assumir que você já saiba tudo — explico cada peça.
Definições e operações usadas por Dijkstra:
  • s é o vértice fonte.
  • Para cada vértice v o algoritmo mantém um valor v.d (estimativa da distância de s até v).
  • \delta(s,v) denota a verdadeira menor distância de s até v no grafo (se v não for alcançável, \delta(s,v)=\infty).
  • Inicialização típica: s.d=0 e, para v\neq s, v.d=\infty.
  • Q é uma fila de prioridade (min-heap) que contém todos os vértices ainda não extraídos; a operação principal é Extract-Min(Q) que remove um vértice u com menor u.d.
  • Relaxar uma aresta (u,v) significa executar: \text{if } v.d > u.d + w(u,v)\\ \text{ then }\\ v.d \leftarrow u.d + w(u,v)\\ \text{ and }\\ v.\pi \leftarrow u.Aqui w(u,v) é o peso da aresta (u,v) (assumimos w(u,v)\ge 0), e v.\pi é o predecessor de v na árvore de caminhos.
  • Invariante importante do Dijkstra (forma usual): no momento em que um vértice u é extraído de Q, temos u.d = \delta(s,u) — ou seja, seu valor está finalizado e é correto.

Passo 3

Explico por que a invariância mencionada acima é verdadeira (passo fundamental para a prova). Vou quebrar esse argumento em fatias pequenas e bem explicadas.
  1. Inicialmente, antes de qualquer extração, s.d=0 e os demais v.d=\infty. Portanto o primeiro Extract-Min(Q) vai retirar s (porque s.d=0 é o menor).
  2. Suponha que, em algum momento, extraímos um vértice u. Pelo princípio do algoritmo e pelos pesos não-negativos, quando extraímos u já não existe caminho de s a nenhum vértice ainda em Q que possa reduzir u.d — porque qualquer caminho que terminasse em u e passasse por vértices ainda em Q teria uma prefixo cujo último vértice também estaria em Q e teria d maior ou igual ao de u, contradizendo o fato de u ser o mínimo. Formalizando de forma simples: extraímos em ordem não decrescente de distâncias estimadas e só podemos reduzir estimativas de vértices que ainda estão em Q relaxando arestas a partir de vértices extraídos; portanto, quando extraímos u sua estimativa já é a distância mínima real \delta(s,u).
  3. Depois de extrair u, o algoritmo relaxa todas as arestas (u,v). Essas relaxações atualizam estimativas de vértices ainda em Q. Repetindo esse processo, o algoritmo garante que, ao extrair cada vértice, sua d já é a distância mínima.
Isso é a razão pela qual a extração final de cada vértice é o momento que “fixa” sua distância correta.

Passo 4

Agora examino especificamente a mudança proposta: parar o laço quando |Q|=1 (ou seja, não extrair o último vértice que restaria em Q). O que acontece nesse ponto do algoritmo, logo antes de encerrar?
  • Ao parar com |Q|=1, o conjunto S dos vértices já extraídos tem tamanho |S| = |V|-1.
  • Resta exatamente um vértice r que nunca foi extraído e ainda está em Q.
A questão chave: será que esse vértice r já tem r.d = \delta(s,r) no momento em que resta apenas ele em Q? Se sim, então não precisamos extraí-lo para obter a solução correta.

Passo 5

Prova elementar de que o último vértice também já tem seu valor finalizado quando ele é o único restante.
Considere o vértice r que ficou em Q. Tome um caminho mais curto (um caminho de comprimento \delta(s,r)) de s até r — se r não for alcançável, então \delta(s,r)=\infty e r.d permanece \infty, então também está correto. Suponha agora que r seja alcançável e que exista um caminho de s até r de comprimento mínimo. Esse caminho tem pelo menos uma aresta (a menos que r=s, caso em que s teria sido extraído primeiro), então o último vértice antes de r nesse caminho mínimo é algum u\neq r.
Porque apenas r não foi extraído, necessariamente u pertence ao conjunto S (os vértices já extraídos). Quando u foi extraído, o algoritmo relaxou a aresta (u,r). Naquele momento, por invariância do algoritmo, u.d = \delta(s,u). Assim, ao relaxar (u,r) fez-se
r.d \le u.d + w(u,r) = \delta(s,u) + w(u,r) = \delta(s,r),
pois \delta(s,r)=\delta(s,u)+w(u,r) (por ser o caminho mínimo). Mas por definição de estimativa não podemos ter r.d < \delta(s,r) (nenhuma estimativa é menor que a verdadeira distância mínima), então necessariamente
r.d = \delta(s,r).
Portanto, no instante em que resta apenas r em Q, já vale r.d=\delta(s,r).
Observe que o argumento também cobre o caso em que r é inacessível: nesse caso \delta(s,r)=\infty e nenhum relax atualizou r.d, de modo que r.d=\infty também está correto.

Passo 6

Tratamento de casos extremos e verificação intuitiva:
  • Caso s fosse o último vértice restante — isso não pode acontecer, porque s.d=0 é o menor valor inicial e s será extraído primeiro. Logo s nunca ficará como último.
  • Caso o grafo seja desconexo: vértices inatingíveis mantém v.d=\infty; não extraí-los não altera correção (o algoritmo retorna \infty corretamente).
  • Para grafos com |V|=1, o laço while |Q|>1 não executa (pois já |Q|=1), e isto está correto: a distância de s para si mesmo é 0, que já foi inicializada.

Passo 7

Conclusão formal e comentário final sobre a complexidade:
  • Como mostramos, quando o laço chega a ter um único vértice em Q esse vértice já tem sua distância final correta. Portanto extrair esse último vértice não altera nem a correção do resultado; é uma iteração redundante em termos de cálculo de distâncias finais. Assim, o algoritmo proposto (com while \(|Q|>1\)) ainda produz as distâncias mínimas corretas \delta(s,v) para todo vértice v.
  • Quanto à complexidade, a extração final a menos poderia poupar uma operação de Extract-Min (e as relaxações a partir desse último vértice não são feitas), então a correção permanece e o tempo poderia ficar ligeiramente menor por constante, mas isso não altera a classe assintótica usualmente considerada (a menos de detalhes da implementação de Q).

Resposta

Sim.

Exercícios relacionados