1. 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 P, uma aresta posterior de P é relaxada antes de uma aresta anterior de P.

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 (u,v) com peso w(u,v). O relaxamento de (u,v) tenta melhorar a estimativa de distância de v usando a estimativa de u. Formalmente, ao relaxar (u,v) fazemos:
\text{se } d[v] > d[u] + w(u,v) \text{ então } d[v] := d[u] + w(u,v),\\ \pi[v] := u.ã
Aqui d[x] é a estimativa atual da distância da fonte s até x, e \pi[x] é o predecessor de x na árvore de caminhos atuais.
Como Dijkstra funciona (resumo necessário): inicializamos d[s]=0 e d[x]=\infty para x\neq s. Mantemos uma fila de prioridade mínima (por d[\cdot]). Repetimos: extraímos um vértice u com menor d[u] finalizado, e então relaxamos todas as arestas que saem de u. Assim, as arestas são relaxadas quando suas caudas são extraídas. Observação importante: quando há empates em d[\cdot] 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 P = \langle s=v_0, v_1, v_2, \dots, v_k\rangle. A ordem natural das arestas em P é (v_0,v_1), (v_1,v_2), \dots, (v_{k-1},v_k). A afirmação do professor Newman seria: ao executar Dijkstra, cada aresta (v_i,v_{i+1}) seria relaxada antes de qualquer aresta (v_j,v_{j+1}) com j>i. 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: \{s,a,b,t\} com s sendo a fonte.
Arestas dirigidas e pesos:
(s,a)\\ \text{com peso}\\\ 1,
(s,b)\\ \text{com peso}\\\ 1,
(a,b)\\ \text{com peso}\\\ 0,
(b,t)\\ \text{com peso}\\\ 1.
Desenho mental: do s saem duas arestas de peso 1, uma para a e outra para b. De a há uma aresta de peso 0 para b. De b vai uma aresta de peso 1 para t.
Obs.: todos os pesos são não negativos (Dijkstra requer isso), e eu usei peso 0 em (a,b) — 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
P = \langle s, a, b, t\rangle,
que usa as arestas (s,a), (a,b), (b,t). Vamos calcular o comprimento de P:
\text{comprimento}(P) = w(s,a) + w(a,b) + w(b,t) = 1 + 0 + 1 = 2.
Compare com o caminho alternativo direto \langle s,b,t\rangle:
\text{comprimento}(\langle s,b,t\rangle) = w(s,b) + w(b,t) = 1 + 1 = 2.
Portanto, ambos os caminhos têm comprimento 2; em particular P é um caminho mínimo de s para t (pode haver empates). O que importa: P é um caminho mínimo e tem arestas em ordem (s,a), (a,b), (b,t).

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:
d[s]=0,\quad d[a]=\infty,\quad d[b]=\infty,\quad d[t]=\infty.
  1. Extraímos s (único com d=0). Ao extrair s relaxamos suas arestas:
  • Relaxar (s,a): como d[a] > d[s] + w(s,a) (isto é, \infty > 0 + 1), atualizamos d[a] := 1 e \pi[a] := s.
  • Relaxar (s,b): como d[b] > d[s] + w(s,b) (isto é, \infty > 0 + 1), atualizamos d[b] := 1 e \pi[b] := s.
Após relaxar arestas de s temos:
d[a]=1,\quad d[b]=1,\quad d[t]=\infty.
Observe que a e b têm exatamente o mesmo valor d=1. A fila de prioridade contém a e b com chave 1; o algoritmo pode desempatar arbitrariamente entre eles.
  1. Suponha que o desempate escolha extrair b antes de a (isto é perfeitamente possível — Dijkstra não fixa uma ordem única quando há empates). Ao extrair b relaxamos a aresta (b,t):
  • Relaxar (b,t): como d[t] > d[b] + w(b,t) (isto é, \infty > 1 + 1), atualizamos d[t] := 2 e \pi[t] := b.
Neste momento a aresta (b,t) (que é a terceira aresta do caminho P=\langle s,a,b,t\rangle) foi relaxada. Repare que a aresta anterior (a,b) do mesmo caminho P ainda não foi relaxada, pois só será relaxada quando a for extraído.
  1. Depois extraímos a (ou o algoritmo faria isso se ainda resta). Ao extrair a relaxamos (a,b):
  • Relaxar (a,b): verificamos d[b] contra d[a] + w(a,b). Temos d[b]=1 e d[a] + w(a,b) = 1 + 0 = 1. Como não é estritamente menor, não atualizamos d[b]. A relaxação não muda nada nesta execução.
Resultado da sequência: a aresta (b,t) foi relaxada no passo 2 (quando b foi extraído), enquanto a aresta anterior (a,b) foi relaxada apenas depois, no passo 3 (quando a foi extraído). Ou seja, no que diz respeito às relaxações efetuadas pelo algoritmo, uma aresta posterior de P foi relaxada antes de uma aresta anterior de P.

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í, P=\langle s,a,b,t\rangle é um caminho mínimo, mas Dijkstra (com desempate que extrai b antes de a) relaxa a aresta (b,t) antes da aresta (a,b). 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 P 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 \{s,a,b,t\} e arestas (s,a) com peso 1, (s,b) com peso 1, (a,b) com peso 0 e (b,t) com peso 1. O caminho P=\langle s,a,b,t\rangle tem comprimento 1+0+1=2 (é um caminho mínimo). Se, após relaxar arestas de s, Dijkstra desempatar e extrair b antes de a, então (b,t) será relaxada antes de (a,b). Assim, Dijkstra pode relaxar arestas de um caminho mínimo fora da ordem.

Exercícios relacionados