1. Exercício 24.3-2 do CLRS3 ou CLRS2. Dê um exemplo simples de grafo dirigido com arestas de peso negativo para o qual o algoritmo de Dijkstra produz respostas incorretas.

Passo 1

O enunciado pede: “Dê um exemplo simples de grafo dirigido com arestas de peso negativo para o qual o algoritmo de Dijkstra produz respostas incorretas.”
Informações relevantes fornecidas pelo enunciado (o que precisamos entregar):
  • Um grafo dirigido simples (vértices e arestas com pesos) que contenha pelo menos uma aresta com peso negativo.
  • Mostrar que, ao aplicar o algoritmo de Dijkstra a partir de um vértice-fonte s, o algoritmo devolve uma distância incorreta para algum vértice.
  • Mostrar qual é a distância correta (verdadeira) e qual é a distância que Dijkstra calcula (incorreta).

Passo 2

Breve explicação (didática) de como funciona o algoritmo de Dijkstra — sem pular etapas:
  • Objetivo: encontrar distâncias mínimas do vértice-fonte s para todos os outros vértices.
  • Inicialização: para cada vértice v definimos uma estimativa de distância \,d(v)\, com
d(s)=0,\qquad d(v)=\infty\\ \text{para }v\neq s.
  • Operação principal: repetimos até todos os vértices serem retirados da fila:
    1. Extraímos (settle) um vértice u com menor d(u) entre os ainda não extraídos.
    2. Para cada aresta (u,v) relaxamos: se \,d(u)+w(u,v)<d(v)\, então atualizamos d(v)\leftarrow d(u)+w(u,v) (isso é chamado de operação decrease-key se usamos uma fila de prioridade).
  • Ideia intuitiva: Dijkstra é “guloso” — assume que quando extrai um vértice u com menor estimativa d(u), essa estimativa já é a distância mínima final para u. Essa suposição é verdadeira quando todos os pesos de aresta são não-negativos.
  • Por que precisa de pesos não-negativos? Porque a prova de corretude usa o fato de que passar por arestas adicionais não pode diminuir o custo se todos os pesos são \ge 0. Se houver arestas de peso negativo, pode existir um caminho que passe por vértices ainda não processados e que diminua a distância de um vértice já finalizado — e Dijkstra não revisita vértices finalizados.

Passo 3

Explicação didática da propriedade usada por Dijkstra (por que falha com arestas negativas):
  • Propriedade (intuição): quando todos os pesos são \ge 0, se u é o vértice extraído com menor d(u) entre os não extraídos, então não existe caminho não visto que leve a u com custo menor que d(u). Isso garante que d(u) é definitivo.
  • Porque isso depende de não-negatividade: qualquer caminho alternativo para u que passe por vértices ainda não extraídos teria, necessariamente, uma parte final com custo \ge 0, de forma que o custo total não pode ser menor que d(u). Se existir uma aresta com peso negativo que faz parte de um caminho alternativo para u e essa aresta sai de um vértice que ainda será descoberto depois, então esse caminho alternativo pode reduzir o custo de u depois que u já foi finalizado — e Dijkstra não permite corrigir isso. É exatamente aí que ele falha.

Passo 4

Apresento um exemplo simples (muito usado e pequeno) que ilustra claramente a falha. Defino o grafo dirigido com vértices \{s,a,b,c\} e arestas orientadas com pesos:
\begin{aligned} &s\to a \quad\text{com peso}\quad 3,\\\ &s\to b \quad\text{com peso}\quad 4,\\\ &b\to c \quad\text{com peso}\quad -6,\\\ &c\to a \quad\text{com peso}\quad 1. \end{aligned}
Observação: aqui eu escolhi esses valores para que exista um caminho de s até a passando por b e c cujo custo é menor que a aresta direta s\to a, e a aresta b\to c é a aresta negativa. Não há ciclo de peso negativo neste grafo (não há ciclo fechado com soma de pesos negativa), portanto as distâncias mínimas estão bem definidas.

Passo 5

Calculemos primeiro a distância correta (a mais baixa possível) de s até cada vértice (intuição e contas passo a passo):
  • Caminhos triviais:
    • s\to a tem custo 3.
    • s\to b tem custo 4.
    • Não há aresta direta s\to c, então inicialmente c parece \infty.
  • Mas existe o caminho s\to b\to c\to a. O custo desse caminho é
4 + (-6) + 1 = -1.
Portanto o menor custo real de s até a é -1 (via b,c), que é menor do que o custo direto 3.
  • Distâncias verdadeiras a partir de s:
    • d_{\text{verd}}(s)=0.
    • d_{\text{verd}}(b)=4 (único caminho simples conhecido direto).
    • d_{\text{verd}}\text{(c)}=4+(-6)=-2 (via s\to b\to c).
    • d_{\text{verd}}(a)=-1 (via s\to b\to c\to a).

Passo 6

Agora executamos Dijkstra (passo a passo, mostrando as estimativas \,d(\cdot)\, e qual vértice é extraído em cada iteração). Inicialização:
d(s)=0,\qquad d(a)=3,\qquad d(b)=4,\qquad d\text{(c)}=\infty.
Fila de prioridade ordenada por d: (s:0),(a:3),(b:4),(c:\infty).
Iteração 1:
  • Extraímos s (o menor, d(s)=0). Relaxamos arestas saindo de s:
    • Relax s\to a: d(a) já é 3, não muda (candidate 0+3=3).
    • Relax s\to b: d(b) já é 4, não muda (candidate 0+4=4).
  • Estado após iter 1: d(a)=3,\quad d(b)=4,\quad d\text{(c)}=\infty.
Fila: (a:3),(b:4),(c:\infty).
Iteração 2:
  • Extraímos o vértice com menor d na fila: isso é a com d(a)=3. Importante: Dijkstra agora considera a finalizado; ele não será extraído novamente nem terá sua distância alterada depois que sair da fila.
  • Relaxações a partir de a: não há arestas saindo de a no nosso exemplo (ou, se houver, não importam para diminuir outros), então nada muda.
  • Estado após iter 2: d(a)=3\\ (\text{final}),\quad d(b)=4,\quad d\text{(c)}=\infty.
Fila: (b:4),(c:\infty).
Iteração 3:
  • Extraímos b com d(b)=4. Relaxamos b\to c:
    • Candidate para c é d(b)+w(b,c)=4+(-6)=-2, então atualizamos d\text{(c)}\leftarrow -2.
  • Estado após iter 3: d(a)=3\\ (\text{final}),\quad d(b)=4\\ (\text{final}),\quad d\text{(c)}=-2.
Fila: (c:-2).
Iteração 4:
  • Extraímos c com d\text{(c)}=-2. Relaxamos c\to a:
    • Candidate para a é d\text{(c)}+w(c,a) = -2 + 1 = -1. Isso é menor que d(a)=3. No entanto, a já foi finalizado (extraído) na Iteração 2, portanto o algoritmo de Dijkstra padrão não atualiza mais a. Consequentemente o valor final devolvido por Dijkstra permanece d(a)=3, embora exista um caminho mais barato que dá d(a)=-1.

Passo 7

Interpretação e conclusão do porquê deu errado (didática e empática):
  • O passo crítico foi que Dijkstra extraiu a muito cedo (quando d(a)=3) porque a estimativa direta era menor que a estimativa de b naquele momento. Mais tarde, ao descobrir o caminho através de b e c, apareceu uma distância menor para a, mas a já havia sido marcado como finalizado. Dijkstra não revisita vértices finalizados.
  • Isso mostra concretamente que a suposição de que “quando um vértice é extraído seu d é definitivo” depende de todos os pesos serem não-negativos. A presença da aresta negativa b\to c que reduz o custo de c e, por consequência, possibilita um caminho menor para a, quebra essa suposição.
  • Moral amiga: não entra em pânico com arestas negativas — para esses casos existe o algoritmo de Bellman–Ford, que lida corretamente com arestas negativas (desde que não haja ciclo de peso negativo), embora seja mais lento.

Resposta

Grafo: vértices \{s,a,b,c\} com arestas e pesos
s\to a\\ (3),\qquad s\to b\\ (4),\qquad b\to c\\ (-6),\qquad c\to a\\ (1).
Resultado: Dijkstra (a partir de s) devolve d(a)=3 (incorreto), enquanto a distância correta é d(a)=-1 (via s\to b\to c\to a).

Exercícios relacionados