- 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):
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
, 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
para todos os outros vértices. - Inicialização: para cada vértice
definimos uma estimativa de distância com
- Operação principal: repetimos até todos os vértices serem retirados da fila:
- Extraímos (settle) um vértice
com menor entre os ainda não extraídos. - Para cada aresta
relaxamos: se então atualizamos (isso é chamado de operação decrease-key se usamos uma fila de prioridade).
- Extraímos (settle) um vértice
- Ideia intuitiva: Dijkstra é “guloso” — assume que quando extrai um vértice
com menor estimativa , essa estimativa já é a distância mínima final para . 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
. 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
, se é o vértice extraído com menor entre os não extraídos, então não existe caminho não visto que leve a com custo menor que . Isso garante que é definitivo. - Porque isso depende de não-negatividade: qualquer caminho alternativo para
que passe por vértices ainda não extraídos teria, necessariamente, uma parte final com custo , de forma que o custo total não pode ser menor que . Se existir uma aresta com peso negativo que faz parte de um caminho alternativo para e essa aresta sai de um vértice que ainda será descoberto depois, então esse caminho alternativo pode reduzir o custo de depois que 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
e arestas orientadas com pesos:
Observação: aqui eu escolhi esses valores para que exista um caminho de
até
passando por
e
cujo custo é menor que a aresta direta
, e a aresta
é 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
até cada vértice (intuição e contas passo a passo):
- Caminhos triviais:
-
tem custo . -
tem custo . - Não há aresta direta
, então inicialmente parece .
-
- Mas existe o caminho
. O custo desse caminho é
Portanto o menor custo real de
até
é
(via
), que é menor do que o custo direto
.
- Distâncias verdadeiras a partir de
: -
. -
(único caminho simples conhecido direto). -
(via ). -
(via ).
-
Passo 6
Agora executamos Dijkstra (passo a passo, mostrando as estimativas
e qual vértice é extraído em cada iteração). Inicialização:
Fila de prioridade ordenada por
:
.
Iteração 1:
- Extraímos
(o menor, ). Relaxamos arestas saindo de : - Relax
: já é , não muda (candidate ). - Relax
: já é , não muda (candidate ).
- Relax
- Estado após iter 1:
Fila:
.
Iteração 2:
- Extraímos o vértice com menor
na fila: isso é com . Importante: Dijkstra agora considera finalizado; ele não será extraído novamente nem terá sua distância alterada depois que sair da fila. - Relaxações a partir de
: não há arestas saindo de no nosso exemplo (ou, se houver, não importam para diminuir outros), então nada muda. - Estado após iter 2:
Fila:
.
Iteração 3:
- Extraímos
com . Relaxamos : - Candidate para
é , então atualizamos .
- Candidate para
- Estado após iter 3:
Fila:
.
Iteração 4:
- Extraímos
com . Relaxamos : - Candidate para
é . Isso é menor que . No entanto, já foi finalizado (extraído) na Iteração 2, portanto o algoritmo de Dijkstra padrão não atualiza mais . Consequentemente o valor final devolvido por Dijkstra permanece , embora exista um caminho mais barato que dá .
- Candidate para
Passo 7
Interpretação e conclusão do porquê deu errado (didática e empática):
- O passo crítico foi que Dijkstra extraiu
muito cedo (quando ) porque a estimativa direta era menor que a estimativa de naquele momento. Mais tarde, ao descobrir o caminho através de e , apareceu uma distância menor para , mas 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
é definitivo” depende de todos os pesos serem não-negativos. A presença da aresta negativa que reduz o custo de e, por consequência, possibilita um caminho menor para , 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
com arestas e pesos
Resultado: Dijkstra (a partir de
) devolve
(incorreto), enquanto a distância correta é
(via
).