- Exercício 24.3-5 do CLRS3 ou CLRS2. O professor Newman acha que criou uma prova simples da correção do algoritmo para o algoritmo de Dijkstra. Diz ele que o algoritmo de Dijkstra relaxa as arestas de todos os caminhos mínimos no grafo na ordem em que eles aparecem no caminho e que, portanto, a propriedade de relaxamento de caminho se aplica a todos os vértices que podem ser alcançados da fonte. Mostre que o professor está enganado ao construir um grafo dirigido para o qual o algoritmo de Dijkstra poderia relaxar as arestas de um caminho mínimo fora da ordem.
Passo 1
O enunciado pede que eu mostre que o professor Newman está enganado: preciso construir um grafo dirigido (com pesos não negativos) para o qual o algoritmo de Dijkstra pode relaxar as arestas de um mesmo caminho mínimo fora da ordem em que elas aparecem nesse caminho.
Informações relevantes que o enunciado dá (implícitas): o algoritmo de Dijkstra usa relaxamento de arestas e extrai vértices na ordem de menor estimativa de distância; o objetivo é produzir um contraexemplo concreto (grafo e pesos) e mostrar uma execução do Dijkstra em que, para um caminho mínimo , uma aresta posterior de
é relaxada antes de uma aresta anterior de
.
Informações relevantes que o enunciado dá (implícitas): o algoritmo de Dijkstra usa relaxamento de arestas e extrai vértices na ordem de menor estimativa de distância; o objetivo é produzir um contraexemplo concreto (grafo e pesos) e mostrar uma execução do Dijkstra em que, para um caminho mínimo
Passo 2
Vamos revisar com calma os conceitos que precisamos para entender a construção (não se preocupe, explico passo a passo).
Definição de relaxamento de aresta. Seja uma aresta dirigida
com peso
. O relaxamento de
tenta melhorar a estimativa de distância de
usando a estimativa de
. Formalmente, ao relaxar
fazemos:
Aqui
é a estimativa atual da distância da fonte
até
, e
é o predecessor de
na árvore de caminhos atuais.
Como Dijkstra funciona (resumo necessário): inicializamos
e
para
. Mantemos uma fila de prioridade mínima (por
). Repetimos: extraímos um vértice
com menor
finalizado, e então relaxamos todas as arestas que saem de
. Assim, as arestas são relaxadas quando suas caudas são extraídas. Observação importante: quando há empates em
a fila de prioridade pode escolher arbitrariamente qual vértice empatará ser extraído primeiro (o algoritmo padrão não especifica um critério de desempate).
O que significa “relaxar as arestas de um caminho mínimo na ordem em que elas aparecem no caminho”? Considere um caminho mínimo
. A ordem natural das arestas em
é
. A afirmação do professor Newman seria: ao executar Dijkstra, cada aresta
seria relaxada antes de qualquer aresta
com
. Vou produzir um grafo em que isso não acontece (ou seja, alguma aresta posterior é relaxada antes de uma anterior).
Passo 3
Construção do grafo exemplo (bem simples e didático). Vou definir vértices e arestas com pesos:
Vértices:
com
sendo a fonte.
Arestas dirigidas e pesos:
Desenho mental: do
saem duas arestas de peso
, uma para
e outra para
. De
há uma aresta de peso
para
. De
vai uma aresta de peso
para
.
Obs.: todos os pesos são não negativos (Dijkstra requer isso), e eu usei peso
em
— permitido e frequente em exemplos.
Passo 4
Verificação de que existe um caminho mínimo cujo relaxamento pode ser feito fora de ordem. Considere o caminho
que usa as arestas
. Vamos calcular o comprimento de
:
Compare com o caminho alternativo direto
:
Portanto, ambos os caminhos têm comprimento
; em particular
é um caminho mínimo de
para
(pode haver empates). O que importa:
é um caminho mínimo e tem arestas em ordem
.
Passo 5
Agora simulo a execução do algoritmo de Dijkstra passo a passo para mostrar a ordem de relaxamentos — e vou escolher o desempate que demonstra o contraexemplo (lembre que desempate pode ser arbitrário).
Inicialização:
- Extraímos
(único com ). Ao extrair relaxamos suas arestas:
- Relaxar
: como (isto é, ), atualizamos e . - Relaxar
: como (isto é, ), atualizamos e .
Após relaxar arestas de
temos:
Observe que
e
têm exatamente o mesmo valor
. A fila de prioridade contém
e
com chave
; o algoritmo pode desempatar arbitrariamente entre eles.
- Suponha que o desempate escolha extrair
antes de (isto é perfeitamente possível — Dijkstra não fixa uma ordem única quando há empates). Ao extrair relaxamos a aresta :
- Relaxar
: como (isto é, ), atualizamos e .
Neste momento a aresta
(que é a terceira aresta do caminho
) foi relaxada. Repare que a aresta anterior
do mesmo caminho
ainda não foi relaxada, pois só será relaxada quando
for extraído.
- Depois extraímos
(ou o algoritmo faria isso se ainda resta). Ao extrair relaxamos :
- Relaxar
: verificamos contra . Temos e . Como não é estritamente menor, não atualizamos . A relaxação não muda nada nesta execução.
Resultado da sequência: a aresta
foi relaxada no passo 2 (quando
foi extraído), enquanto a aresta anterior
foi relaxada apenas depois, no passo 3 (quando
foi extraído). Ou seja, no que diz respeito às relaxações efetuadas pelo algoritmo, uma aresta posterior de
foi relaxada antes de uma aresta anterior de
.
Passo 6
Conclusão lógica do contraexemplo: isto demonstra explicitamente que a afirmação de Newman — que Dijkstra “relaxa as arestas de todos os caminhos mínimos no grafo na ordem em que eles aparecem no caminho” — é falsa. No grafo que construí,
é um caminho mínimo, mas Dijkstra (com desempate que extrai
antes de
) relaxa a aresta
antes da aresta
. A razão técnica é simples e importante: Dijkstra relaxa arestas quando suas caudas são extraídas da fila de prioridade; se dois vértices ao longo do caminho têm estimativas iguais, a ordem de extração pode colocá-los fora da ordem do caminho, e portanto a ordem de relaxamento das arestas de
pode ficar fora de ordem.
Comentário encorajador: isso não significa que Dijkstra esteja errado — o algoritmo continua correto para grafos com pesos não negativos — apenas mostra que a afirmação específica sobre a ordem das relaxações ao longo de cada caminho mínimo é demasiadamente forte e pode falhar em presença de empates (ou de caminhos alternativos de mesmo custo).
Resposta
Um contraexemplo simples é o grafo dirigido com vértices
e arestas
com peso
,
com peso
,
com peso
e
com peso
. O caminho
tem comprimento
(é um caminho mínimo). Se, após relaxar arestas de
, Dijkstra desempatar e extrair
antes de
, então
será relaxada antes de
. Assim, Dijkstra pode relaxar arestas de um caminho mínimo fora da ordem.