- Exercício 24.3-3 do CLRS3 ou CLRS2. Suponha que mudemos a linha 4 do algoritmo de Dijkstra para o seguinte:
Essa mudança faz o laço while ser executado
vezes em lugar de
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
ou seja, fazer o laço vezes em vez de
vezes.
Informações relevantes dadas:
while executar
Informações relevantes dadas:
- O algoritmo considerado é o de Dijkstra (com pesos de arestas não negativos).
- Originalmente o laço
whileiterava enquanto(extraindo todos os vértices). - A proposta faz o laço parar quando resta exatamente um vértice em
.
A pergunta é: esse algoritmo proposto (comwhile \(|Q|>1\)) continua correto (ou seja, ainda calcula as distâncias mínimasdo vértice fonte para todo vértice )?
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:
-
é o vértice fonte. - Para cada vértice
o algoritmo mantém um valor (estimativa da distância de até ). -
denota a verdadeira menor distância de até no grafo (se não for alcançável, ). - Inicialização típica:
e, para , . -
é 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érticecom menor . - Relaxar uma aresta
significa executar: Aqui é o peso da aresta (assumimos ), e é o predecessor de na árvore de caminhos. - Invariante importante do Dijkstra (forma usual): no momento em que um vértice
é extraído de , temos — 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.
-
Inicialmente, antes de qualquer extração,
e os demais . Portanto o primeiro Extract-Min(Q)vai retirar(porque é o menor). -
Suponha que, em algum momento, extraímos um vértice
. Pelo princípio do algoritmo e pelos pesos não-negativos, quando extraímos já não existe caminho de a nenhum vértice ainda em que possa reduzir — porque qualquer caminho que terminasse em e passasse por vértices ainda em teria uma prefixo cujo último vértice também estaria em e teria maior ou igual ao de , contradizendo o fato de 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 relaxando arestas a partir de vértices extraídos; portanto, quando extraímos sua estimativa já é a distância mínima real . -
Depois de extrair
, o algoritmo relaxa todas as arestas . Essas relaxações atualizam estimativas de vértices ainda em . Repetindo esse processo, o algoritmo garante que, ao extrair cada vértice, sua 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
(ou seja, não extrair o último vértice que restaria em
). O que acontece nesse ponto do algoritmo, logo antes de encerrar?
- Ao parar com
, o conjunto dos vértices já extraídos tem tamanho . - Resta exatamente um vértice
que nunca foi extraído e ainda está em .
A questão chave: será que esse vértice
já tem
no momento em que resta apenas ele em
? 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
que ficou em
. Tome um caminho mais curto (um caminho de comprimento
) de
até
— se
não for alcançável, então
e
permanece
, então também está correto. Suponha agora que
seja alcançável e que exista um caminho de
até
de comprimento mínimo. Esse caminho tem pelo menos uma aresta (a menos que
, caso em que
teria sido extraído primeiro), então o último vértice antes de
nesse caminho mínimo é algum
.
Porque apenas
não foi extraído, necessariamente
pertence ao conjunto
(os vértices já extraídos). Quando
foi extraído, o algoritmo relaxou a aresta
. Naquele momento, por invariância do algoritmo,
. Assim, ao relaxar
fez-se
pois
(por ser o caminho mínimo). Mas por definição de estimativa não podemos ter
(nenhuma estimativa é menor que a verdadeira distância mínima), então necessariamente
Portanto, no instante em que resta apenas
em
, já vale
.
Observe que o argumento também cobre o caso em que
é inacessível: nesse caso
e nenhum relax atualizou
, de modo que
também está correto.
Passo 6
Tratamento de casos extremos e verificação intuitiva:
- Caso
fosse o último vértice restante — isso não pode acontecer, porque é o menor valor inicial e será extraído primeiro. Logo nunca ficará como último. - Caso o grafo seja desconexo: vértices inatingíveis mantém
; não extraí-los não altera correção (o algoritmo retorna corretamente). - Para grafos com
, o laço while |Q|>1não executa (pois já), e isto está correto: a distância de para si mesmo é , 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
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 corretaspara todo vértice . - 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).
Resposta
Sim.