Exercício 24.1-4 do CLRS3 ou CLRS2 - Modifique o algoritmo de Belman-Ford de modo que ele termine com v.d como - \infty para todos os vértices v para os quais existe um ciclo de peso negativo em algum caminho da fonte até v.

Passo 1

O que o enunciado pede e quais informações temos.
  • O enunciado: modificar o algoritmo de Bellman–Ford para que, ao terminar, cada vértice v tenha v.d = -\infty sempre que existir algum caminho da fonte s até v que passe por um ciclo de peso negativo.
  • Informações dadas (pressupostas pelo enunciado padrão do Bellman–Ford):
    • Temos um grafo dirigido com pesos nas arestas representado por (V,E).
    • Existe uma função de peso w: E \to \mathbb{R}.
    • Existe uma fonte s \in V.
    • O algoritmo Bellman–Ford clássico inicializa v.d = +\infty para todo v\neq s, s.d = 0, e relaxa todas as arestas repetidas |V|-1 vezes para obter menores caminhos simples; então faz uma passada extra para detectar arestas relaxáveis (o que indica ciclo de peso negativo alcançável).
  • O objetivo explícito aqui: adaptar Bellman–Ford de forma que, além de detectar ciclos de peso negativo alcançáveis, o algoritmo finalize com v.d = -\infty para todo vértice v para o qual existe algum caminho de s até v que contenha (em qualquer lugar do caminho) um ciclo de peso negativo.

Passo 2

Recordando como Bellman–Ford funciona (conceitos necessários, sem pular etapas).
  • Inicialização:
    • Para cada vértice v fazemos v.d \leftarrow +\infty e v.\pi \leftarrow \text{NIL}.
    • Para a fonte fazemos s.d \leftarrow 0.
    • Aqui v.d é a estimativa atual do menor peso de um caminho de s até v; v.\pi é o predecessor no caminho estimado.
  • Operação principal — relaxamento de uma aresta (u,v):
    • A operação “relax” verifica se passando por u conseguimos um caminho melhor para v.
    • Formalmente, se v.d > u.d + w(u,v) então fazemos v.d \leftarrow u.d + w(u,v),\qquad v.\pi \leftarrow u.
    • Essa operação atualiza a estimativa de distância para v caso exista uma rota melhor através de u.
  • Propriedade usada pelo Bellman–Ford:
    • Após repetir o passo de relaxar todas as arestas por |V|-1 iterações, todas as distâncias mínimas de caminhos simples (sem ciclos repetidos) de s até qualquer vértice são encontradas, se não existir ciclo negativo alcançável.
    • Se, depois disso, ainda existe alguma aresta (u,v) com v.d > u.d + w(u,v), então existe um ciclo de peso negativo alcançável a partir de s (pois a distância pode ser reduzida indefinidamente).

Passo 3

Por que precisamos propagar -\infty e o que exatamente significa "ciclo de peso negativo em algum caminho de s até v".
  • Intuição: se existe um ciclo de peso negativo que é alcançável a partir de s e esse ciclo fica em algum ponto de um caminho que leva a v, então podemos percorrer esse ciclo arbitrariamente muitas vezes e diminuir o custo do caminho de s até v sem limite inferior. Logo, o “menor custo” é não limitado, representado por -\infty.
  • Consequência prática: não basta marcar apenas os vértices que pertencem diretamente a ciclos negativos detectados; qualquer vértice que seja alcançável a partir de um vértice que tem acesso a um ciclo negativo também deve receber v.d = -\infty, pois o caminho até esse vértice pode atravessar o ciclo negativo e depois seguir adiante.

Passo 4

Estratégia geral da modificação (alto nível, sem pseudocódigo ainda).
    1. Executar Bellman–Ford padrão: inicialização + |V|-1 passadas de relaxamento de todas as arestas. Após isso, se não existirem arestas relaxáveis, temos as distâncias ótimas; caso contrário, existem ciclos negativos alcançáveis.
    1. Fazer uma passada extra sobre todas as arestas (u,v). Para cada aresta que ainda é relaxável, isto é, para cada (u,v) tal que v.d > u.d + w(u,v), marcamos v como “afetado por ciclo negativo” (porque sua estimativa pode ser reduzida indefinidamente).
    1. Propagar essa marcação para todos os vértices alcançáveis a partir de qualquer vértice marcado. A propagação é um simples passeio em largura/profundidade (BFS/DFS) seguindo arestas orientadas no sentido original; durante a propagação definimos x.d \leftarrow -\infty para cada vértice x marcado ou atingido por marcação.
    1. Ao final, qualquer vértice que foi marcado terá v.d = -\infty; os demais manterão as estimativas corretas de menor caminho (se não atingidos por ciclo negativo).

Passo 5

Pseudocódigo detalhado (etapas implementáveis com clareza). Vou descrever em formato passo a passo com variáveis em TeX.
  • Inicialização:
    • Para cada vértice v: faça v.d \leftarrow +\infty, v.\pi \leftarrow \text{NIL}.
    • Faça s.d \leftarrow 0.
  • Relaxação |V|-1 vezes:
    • Para i \leftarrow 1 até |V|-1:
      • Para cada aresta (u,v)\in E:
        • Se v.d > u.d + w(u,v) então faça v.d \leftarrow u.d + w(u,v),\qquad v.\pi \leftarrow u.
  • Detecção de arestas relaxáveis (identificação inicial de vértices afetados):
    • Crie uma fila/estrutura de marcação vazia Q.
    • Para cada aresta (u,v)\in E:
      • Se v.d > u.d + w(u,v) então:
        • se v.d \neq -\infty então faça v.d \leftarrow -\infty e enfileire v em Q.
        • (Assim garantimos que marcamos v como afetado; reparar que usamos o teste v.d \neq -\infty para não enfileirar várias vezes.)
  • Propagação do -\infty aos alcançáveis:
    • Enquanto Q não estiver vazia:
      • Desenfileire x de Q.
      • Para cada aresta (x,y)\in E:
        • Se y.d \neq -\infty então faça y.d \leftarrow -\infty e enfileire y em Q.
  • Resultado:
    • Ao fim, para cada vértice v alcançável por algum caminho de s que contenha um ciclo de peso negativo, temos v.d = -\infty. Para os demais vértices, v.d é a menor distância finita encontrada (ou +\infty se inacessível).

Passo 6

Explicação intuitiva e prova de corretude (por que a modificação funciona).
  • Depois de |V|-1 iterações de relaxamento todas as menores distâncias por caminhos simples (sem repetição de vértices) são encontradas. Se existe uma aresta (u,v) com v.d > u.d + w(u,v), significa que a estimativa pode ser reduzida usando um caminho que repete vértices — isto só é possível se existe um ciclo de peso negativo em algum prefixo do caminho a v que é alcançável a partir de s.
  • Marcar v sempre que sua aresta é relaxável garante marcar um vértice que tem um caminho de s até ele que passa por um ciclo negativo (o ciclo repetido permite reduzir o custo até v sem limite).
  • Propagar a marca por todas as arestas que saem de um vértice marcado é necessário porque qualquer vértice y alcançável a partir de um vértice marcado x também terá um caminho de s para y que contém esse negativo-ciclo prefixo (basta concatenar o caminho de s até o ciclo, rodar o ciclo arbitrariamente, sair para x e ir até y). Assim y também deve ter custo -\infty.
  • Portanto, todo vértice que deve ficar com -\infty será marcado e receberá v.d = -\infty; vértices não marcados não têm nenhum caminho de s que contenha um ciclo de peso negativo, então suas distâncias finitas estão corretas.

Passo 7

Complexidade e observações para prova/implementação.
  • Complexidade:
    • O Bellman–Ford padrão custa O(|V||E|) para as |V|-1 iterações.
    • A passada extra para detectar arestas relaxáveis custa O(|E|).
    • A propagação por BFS/DFS custa O(|V|+|E|).
    • Assim, a modificação mantém a ordem de complexidade O(|V||E|) dominada pelo passo principal.
  • Observações práticas:
    • Use uma fila (BFS) para evitar marcações repetidas e obter implementação simples.
    • Em implementações reais codifique -\infty com um valor símbolo (por ex. uma constante especial) ou com o tipo que permita representar -\infty.
    • Certifique-se de não confundir vértices inalcançáveis (com v.d = +\infty) com vértices afetados por ciclos negativos (com v.d = -\infty).

Passo 8

Exemplo pequeno (para fixar a ideia) — descrição textual passo a passo.
  • Considere V=\{s,a,b\} e arestas:
    • (s,a) com w=1
    • (a,b) com w=-3
    • (b,a) com w=1 (então o ciclo a\to b\to a tem peso -2, negativo)
  • Executando Bellman–Ford:
    • Inicialmente s.d=0, a.d=+\infty, b.d=+\infty.
    • Após |V|-1=2 iterações as estimativas serão reduzidas indefinidamente se continuarmos: mas concretamente você verá que existe ao menos uma aresta relaxável na passada extra, por exemplo (b,a) relaxa a.d.
    • Na passada extra detectamos arestas relaxáveis e marcamos a (ou b), colocamos a.d \leftarrow -\infty e propagamos: então b também recebe -\infty pois é alcançável de a e vice-versa. Ao final a.d = b.d = -\infty, como desejado.

Passo 9

Pseudocódigo final conciso (pronto para escrever na prova)
  • Inicialização:
    • Para cada v\in V: v.d \leftarrow +\infty, v.\pi \leftarrow \text{NIL}.
    • s.d \leftarrow 0.
  • Para i \leftarrow 1 até |V|-1:
    • Para cada (u,v)\in E: se v.d > u.d + w(u,v) então v.d \leftarrow u.d + w(u,v); v.\pi \leftarrow u.
  • Crie fila Q vazia.
  • Para cada (u,v)\in E:
    • Se v.d > u.d + w(u,v) e v.d \neq -\infty então v.d \leftarrow -\infty; enfileire v em Q.
  • Enquanto Q não estiver vazia :
    • x \leftarrow desenfileira Q.
    • Para cada (x,y)\in E:
      • Se y.d \neq -\infty então y.d \leftarrow -\infty; enfileire y.
  • Fim — agora v.d = -\infty exatamente para os vértices que admitem um caminho de s até v que contenha um ciclo de peso negativo.

Resposta

Executar Bellman–Ford padrão (inicializar; relaxar todas as arestas |V|-1 vezes); em seguida, fazer uma passada extra sobre todas as arestas e para cada aresta (u,v) que ainda seja relaxável (isto é, com v.d > u.d + w(u,v)) definir v.d \leftarrow -\infty e enfileirar v numa fila Q; finalmente propagar o -\infty fazendo BFS/DFS a partir dos vértices em Q ao longo das arestas do grafo, e para cada vértice alcançado definir sua distância como -\infty.

Exercícios relacionados