Bellman-Ford

Quando o peso pode ser negativo

Peso negativo soa artificial até você ver onde ele aparece de verdade:

• Arbitragem de câmbio: cada aresta é uma conversão de moeda, e o peso é o logaritmo negativo da taxa. Um ciclo negativo é literalmente dinheiro de graça.
• Fluxo de caixa: aresta que representa um ganho é custo negativo.
• Jogos e simulações: um trecho pode devolver energia em vez de gastar.
• Grafos de restrição: sistemas de desigualdades do tipo x - y ≤ c viram grafo com pesos que podem ser negativos.

E aparece uma pergunta nova, que só existe nesse mundo: e se dar uma volta num ciclo baratear? Aí você pode dar a volta de novo, e de novo, e o custo desce sem fim. O caminho mínimo simplesmente não existe. Detectar isso é metade do valor do Bellman-Ford.

A ideia: insistir em vez de escolher

O algoritmo inteiro cabe em duas frases. Relaxe todas as arestas. Repita V-1 vezes.

def bellman_ford(inicio, vertices, arestas):
    dist = {v: float("inf") for v in vertices}
    dist[inicio] = 0

    for _ in range(len(vertices) - 1):      # V-1 rodadas
        for u, v, peso in arestas:          # todas as arestas
            if dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso

    for u, v, peso in arestas:              # a rodada que sobra
        if dist[u] + peso < dist[v]:
            raise ValueError("ciclo negativo")
    return dist

Sem fila de prioridade, sem conjunto de fechados, sem decisão nenhuma. O relaxamento é o mesmo do Dijkstra; muda só quem manda na ordem, que aqui é ninguém.

Comece no preset com peso negativo e acompanhe a tabela de rodadas. É esse painel que ensina o algoritmo: cada linha é uma rodada, e as células destacadas são as que mudaram. Repare que a informação se propaga uma aresta por rodada, como uma onda saindo da origem.

Depois vá para o preset ciclo negativo e rode até o fim. A última mensagem é a rodada extra encontrando uma aresta que ainda melhora, e a aresta culpada acende em vermelho no desenho.

De onde sai o V-1

Este é o número que todo mundo decora sem saber de onde vem, e ele tem uma explicação de uma linha.

Um caminho mínimo nunca repete vértice. Se repetisse, haveria um ciclo dentro dele, e como não há ciclo negativo, remover esse ciclo daria um caminho igual ou mais barato. Então o caminho mínimo passa por no máximo V vértices, ou seja, no máximo V-1 arestas.

E aí entra a garantia que a tabela do visualizador mostra:

depois da rodada k, todo caminho mínimo que usa até k arestas já está correto

Rodada 1 acerta os caminhos de 1 aresta. Rodada 2 acerta os de 2. Como nenhum passa de V-1 arestas, V-1 rodadas bastam. Não é margem de segurança nem chute: é o número exato.

A rodada que sobra

Depois das V-1 rodadas, o algoritmo faz mais uma passada. Se alguma aresta ainda melhora, existe ciclo negativo.

A lógica é por absurdo. Se não houvesse ciclo negativo, todo caminho mínimo teria no máximo V-1 arestas e já estaria correto. Melhorar na rodada V significaria um caminho com V arestas melhor que todos os menores, o que só é possível se ele repetir vértice, ou seja, se ele der uma volta que diminui o custo.

Note também que o Bellman-Ford só enxerga ciclos negativos alcançáveis a partir da origem. Um ciclo negativo escondido num componente separado passa despercebido, e a saída é criar uma origem virtual ligada a todos os vértices com peso 0.

Dijkstra ou Bellman-Ford

Com 1.000 vértices e 10.000 arestas, Dijkstra faz cerca de 100 mil operações e Bellman-Ford cerca de 10 milhões. Não é detalhe: é 100 vezes.

A regra prática é direta: use Dijkstra sempre que puder, e Bellman-Ford quando precisar. Precisar quer dizer peso negativo, necessidade de detectar ciclo negativo, ou a restrição de "no máximo k arestas".

Duas otimizações honestas

A primeira é gratuita: se uma rodada inteira não mudar nada, pare. Nenhuma rodada seguinte mudaria, porque a entrada dela seria idêntica. Em grafo comum isso costuma cortar boa parte das rodadas, e o visualizador já faz isso (repare quando ele encerra antes das V-1 rodadas).

for _ in range(len(vertices) - 1):
    mudou = False
    for u, v, peso in arestas:
        if dist[u] + peso < dist[v]:
            dist[v] = dist[u] + peso
            mudou = True
    if not mudou:
        break                     # convergiu antes

A segunda é o SPFA (Shortest Path Faster Algorithm): em vez de relaxar todas as arestas toda rodada, mantenha uma fila só com os vértices cuja distância mudou, já que só eles podem melhorar alguém. Na média fica muito mais rápido, mas o pior caso continua O(V·E), e existem grafos construídos de propósito para derrubá-lo. É bom saber que existe e arriscado usar em competição.

Como praticar

Cheapest Flights Within K Stops é o problema que faz o Bellman-Ford brilhar, justamente por causa da propriedade das k rodadas. Vale tentar primeiro com Dijkstra e ver a resposta sair errada: entender por que ele erra ali ensina mais do que acertar de primeira. A dica é que, com a restrição de paradas, um caminho mais caro pode ser preferível por usar menos arestas, e o Dijkstra descarta esse caminho cedo.

Network Delay Time aceita os dois algoritmos, então é um bom lugar para implementar Bellman-Ford e comparar o tempo com a sua solução de Dijkstra no mesmo problema.

Depois, procure por problemas de arbitragem de moedas, que são a aplicação mais bonita da detecção de ciclo negativo: transformar taxas em -log(taxa) faz "multiplicação de taxas maior que 1" virar "soma de pesos menor que 0", e o ciclo negativo passa a significar lucro garantido.

Daqui, Floyd-Warshall resolve todos os pares de uma vez e também detecta ciclo negativo, e o A* vai para o lado oposto: aceita menos generalidade em troca de muito mais velocidade quando você sabe alguma coisa sobre o destino.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 2:22:53.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.

Este tópico também tem página própria, fora deste roadmap: Bellman-Ford.