Exercício 24.1-4 do CLRS3 ou CLRS2 - Modifique o algoritmo de Belman-Ford de modo que ele termine com v.d como -
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
tenha sempre que existir algum caminho da fonte até 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
. - Existe uma função de peso
. - Existe uma fonte
. - O algoritmo Bellman–Ford clássico inicializa
para todo , , e relaxa todas as arestas repetidas 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).
- Temos um grafo dirigido com pesos nas arestas representado por
- 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
para todo vértice para o qual existe algum caminho de até 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
fazemos e . - Para a fonte fazemos
. - Aqui
é a estimativa atual do menor peso de um caminho de até ; é o predecessor no caminho estimado.
- Para cada vértice
- Operação principal — relaxamento de uma aresta
: - A operação “relax” verifica se passando por
conseguimos um caminho melhor para . - Formalmente, se
então fazemos - Essa operação atualiza a estimativa de distância para
caso exista uma rota melhor através de .
- A operação “relax” verifica se passando por
- Propriedade usada pelo Bellman–Ford:
- Após repetir o passo de relaxar todas as arestas por
iterações, todas as distâncias mínimas de caminhos simples (sem ciclos repetidos) de até qualquer vértice são encontradas, se não existir ciclo negativo alcançável. - Se, depois disso, ainda existe alguma aresta
com , então existe um ciclo de peso negativo alcançável a partir de (pois a distância pode ser reduzida indefinidamente).
- Após repetir o passo de relaxar todas as arestas por
Passo 3
Por que precisamos propagar
e o que exatamente significa "ciclo de peso negativo em algum caminho de
até
".
- Intuição: se existe um ciclo de peso negativo que é alcançável a partir de
e esse ciclo fica em algum ponto de um caminho que leva a , então podemos percorrer esse ciclo arbitrariamente muitas vezes e diminuir o custo do caminho de até sem limite inferior. Logo, o “menor custo” é não limitado, representado por . - 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
, 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).
-
- Executar Bellman–Ford padrão: inicialização +
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.
- Executar Bellman–Ford padrão: inicialização +
-
- Fazer uma passada extra sobre todas as arestas
. Para cada aresta que ainda é relaxável, isto é, para cada tal que , marcamos como “afetado por ciclo negativo” (porque sua estimativa pode ser reduzida indefinidamente).
- Fazer uma passada extra sobre todas as arestas
-
- 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
para cada vértice marcado ou atingido por marcação.
- 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
-
- Ao final, qualquer vértice que foi marcado terá
; os demais manterão as estimativas corretas de menor caminho (se não atingidos por ciclo negativo).
- Ao final, qualquer vértice que foi marcado terá
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
: faça , . - Faça
.
- Para cada vértice
- Relaxação
vezes: - Para
até : - Para cada aresta
: - Se
então faça
- Se
- Para cada aresta
- Para
- Detecção de arestas relaxáveis (identificação inicial de vértices afetados):
- Crie uma fila/estrutura de marcação vazia
. - Para cada aresta
: - Se
então: - se
então faça e enfileire em . - (Assim garantimos que marcamos
como afetado; reparar que usamos o teste para não enfileirar várias vezes.)
- se
- Se
- Crie uma fila/estrutura de marcação vazia
- Propagação do
aos alcançáveis: - Enquanto
não estiver vazia: - Desenfileire
de . - Para cada aresta
: - Se
então faça e enfileire em .
- Se
- Desenfileire
- Enquanto
- Resultado:
- Ao fim, para cada vértice
alcançável por algum caminho de que contenha um ciclo de peso negativo, temos . Para os demais vértices, é a menor distância finita encontrada (ou se inacessível).
- Ao fim, para cada vértice
Passo 6
Explicação intuitiva e prova de corretude (por que a modificação funciona).
- Depois de
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 com , 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 que é alcançável a partir de . - Marcar
sempre que sua aresta é relaxável garante marcar um vértice que tem um caminho de até ele que passa por um ciclo negativo (o ciclo repetido permite reduzir o custo até sem limite). - Propagar a marca por todas as arestas que saem de um vértice marcado é necessário porque qualquer vértice
alcançável a partir de um vértice marcado também terá um caminho de para que contém esse negativo-ciclo prefixo (basta concatenar o caminho de até o ciclo, rodar o ciclo arbitrariamente, sair para e ir até ). Assim também deve ter custo . - Portanto, todo vértice que deve ficar com
será marcado e receberá ; vértices não marcados não têm nenhum caminho de 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
para as iterações. - A passada extra para detectar arestas relaxáveis custa
. - A propagação por BFS/DFS custa
. - Assim, a modificação mantém a ordem de complexidade
dominada pelo passo principal.
- O Bellman–Ford padrão custa
- Observações práticas:
- Use uma fila (BFS) para evitar marcações repetidas e obter implementação simples.
- Em implementações reais codifique
com um valor símbolo (por ex. uma constante especial) ou com o tipo que permita representar . - Certifique-se de não confundir vértices inalcançáveis (com
) com vértices afetados por ciclos negativos (com ).
Passo 8
Exemplo pequeno (para fixar a ideia) — descrição textual passo a passo.
- Considere
e arestas: -
com -
com -
com (então o ciclo tem peso , negativo)
-
- Executando Bellman–Ford:
- Inicialmente
, , . - Após
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 relaxa . - Na passada extra detectamos arestas relaxáveis e marcamos
(ou ), colocamos e propagamos: então também recebe pois é alcançável de e vice-versa. Ao final , como desejado.
- Inicialmente
Passo 9
Pseudocódigo final conciso (pronto para escrever na prova)
- Inicialização:
- Para cada
: , . -
.
- Para cada
- Para
até : - Para cada
: se então ; .
- Para cada
- Crie fila
vazia. - Para cada
: - Se
e então ; enfileire em .
- Se
- Enquanto
não estiver vazia -
desenfileira . - Para cada
: - Se
então ; enfileire .
- Se
-
- Fim — agora
exatamente para os vértices que admitem um caminho de até que contenha um ciclo de peso negativo.
Resposta
Executar Bellman–Ford padrão (inicializar; relaxar todas as arestas
vezes); em seguida, fazer uma passada extra sobre todas as arestas e para cada aresta
que ainda seja relaxável (isto é, com
) definir
e enfileirar
numa fila
; finalmente propagar o
fazendo BFS/DFS a partir dos vértices em
ao longo das arestas do grafo, e para cada vértice alcançado definir sua distância como
.