Bellman-Ford e ciclos negativos
Execute n-1 passagens de relaxamento sobre todas as arestas, detecte ciclos negativos com uma passagem final e explique por que Dijkstra falha em arestas com pesos negativos.
Bellman-Ford e ciclos negativos é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Por que Bellman-Ford existe
Bellman-Ford resolve o problema do caminho mais curto a partir de uma única origem, assim como Dijkstra, mas trata pesos negativos nas arestas. Ele também detecta ciclos negativos — ciclos cuja soma dos pesos é negativa, o que impossibilita definir um caminho mais curto finito que passe por eles. Embora seja mais lento que Dijkstra, Bellman-Ford é a escolha correta sempre que o grafo puder conter arestas de peso negativo.
Relaxamento: a operação principal
Bellman-Ford é construído sobre uma única operação: o relaxamento. Relaxar a aresta (u, v, w) significa: se dist[u] + w < dist[v], atualize dist[v] = dist[u] + w. Repetimos o relaxamento de todas as arestas. A ideia principal é: qualquer caminho mais curto tem no máximo V-1 arestas (em um grafo sem ciclos negativos). Portanto, V-1 rodadas de relaxamento sobre todas as arestas são suficientes para encontrar todos os caminhos mais curtos.
Implementação de Bellman-Ford
Represente o grafo como uma lista de arestas [(u, v, weight)]. Inicialize dist[source] = 0 e atribua inf a todos os demais elementos. Execute V-1 rodadas, relaxando todas as arestas em cada rodada. Qualquer atualização que ainda ocorra em uma V-ésima rodada indica um ciclo negativo.
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]Por que V-1 passagens são suficientes
Um caminho mais curto em um grafo sem ciclos negativos visita cada nó no máximo uma vez, portanto tem no máximo V-1 arestas. Depois da rodada 1, os caminhos mais curtos com 1 salto são ótimos. Depois da rodada 2, os caminhos mais curtos com 2 saltos são ótimos. Depois de V-1 rodadas, todos os caminhos mais curtos (que usam no máximo V-1 saltos) foram encontrados. Se a rodada V ainda atualizar uma distância, o grafo contém um ciclo negativo alcançável a partir da origem.
Detecção de ciclos negativos
Depois de V-1 passagens, execute uma passagem adicional sobre todas as arestas. Se alguma aresta (u, v, w) satisfizer dist[u] + w < dist[v], então existe um ciclo negativo e o caminho mais curto até alguns nós é -infinity. Entre as aplicações reais estão a detecção de oportunidades de arbitragem no câmbio de moedas (ciclos negativos em grafos com pesos logarítmicos) e a detecção de inconsistências em sistemas de restrições.
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # TrueComparação entre Dijkstra e Bellman-Ford
Dijkstra: O((V+E) log V), exige pesos não negativos e usa uma abordagem gulosa. Bellman-Ford: O(V × E), trata pesos negativos e detecta ciclos negativos. Para a maioria dos problemas de entrevista com pesos não negativos, Dijkstra é preferível. Quando aparecem pesos negativos (por exemplo, “encontrar o caminho mais curto com arestas de custo negativo” ou “detectar arbitragem”), Bellman-Ford é a resposta. Para grafos densos, o pior caso O(V³) de Bellman-Ford é comparável ao de Floyd-Warshall.
Aplicação: voos mais baratos com Bellman-Ford
Voos mais baratos com no máximo K escalas (LeetCode 787) pode ser resolvido com um Bellman-Ford modificado: execute exatamente k+1 passagens de relaxamento (pois k escalas significam k+1 arestas). Use uma cópia das distâncias da passagem anterior para garantir que não usemos mais saltos do que o permitido em uma única passagem — caso contrário, uma única passagem poderia encadear vários saltos.
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: otimização baseada em fila
O Shortest Path Faster Algorithm (SPFA) é um Bellman-Ford otimizado que relaxa novamente apenas as arestas dos nós cuja distância acabou de ser atualizada, usando uma fila. O caso médio é O(E), mas o pior caso continua sendo O(V × E). SPFA raramente é necessário em entrevistas, mas você pode mencioná-lo como uma otimização quando Bellman-Ford for lento demais em grafos esparsos. O Python não tem um SPFA integrado, mas é simples implementá-lo com collections.deque.
Detecção de arbitragem cambial
Uma aplicação clássica de Bellman-Ford: dadas as taxas de câmbio, detecte se é possível fazer arbitragem (um ciclo no qual a conversão das moedas retorna mais do que o valor inicial). Faça a transformação calculando o logaritmo negativo das taxas de câmbio. Arbitragem = um ciclo com peso logarítmico total negativo = ciclo negativo detectável por Bellman-Ford. Isso mapeia problemas financeiros do mundo real para o algoritmo padrão.
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return FalseOtimização por encerramento antecipado
Se nenhuma distância for atualizada em uma passagem completa por todas as arestas, as passagens seguintes também não atualizarão nada — encerre antecipadamente. Essa otimização reduz a complexidade do melhor caso para O(E) quando o grafo já está ótimo após poucas passagens. Adicione um sinalizador updated = False no início de cada passagem; se ele continuar como False depois da passagem, interrompa imediatamente.
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distBellman-Ford em grafos com listas de adjacência
Quando o grafo é fornecido como uma lista de adjacência, e não como uma lista de arestas, converta-o primeiro para uma lista de arestas ou percorra todas as entradas da lista de adjacência como arestas. Para V=1000 e E=5000, V-1=999 passagens, cada uma percorrendo 5000 arestas, resultam em 4.995.000 operações — bem dentro dos limites de tempo. Para grafos muito densos (E ≈ V²), o pior caso O(V³) coincide com o de Floyd-Warshall, portanto a escolha depende do contexto.
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distVerificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: Bellman-Ford relaxa todas as arestas V-1 vezes para tratar arestas de peso negativo, uma V-ésima passagem de relaxamento que ainda encontra melhorias indica um ciclo negativo e o algoritmo é O(V × E), em comparação com O((V+E) log V) de Dijkstra. Em seguida, veremos Floyd-Warshall para encontrar os caminhos mais curtos entre todos os pares em um único cálculo O(V³).
Perguntas Frequentes
A aula “Bellman-Ford e ciclos negativos” é grátis?
Sim — o texto completo de “Bellman-Ford e ciclos negativos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Bellman-Ford e ciclos negativos”?
Execute n-1 passagens de relaxamento sobre todas as arestas, detecte ciclos negativos com uma passagem final e explique por que Dijkstra falha em arestas com pesos negativos. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Bellman-Ford e ciclos negativos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Algoritmo de Dijkstra com fila de prioridades
- Bellman-Ford e ciclos negativos
- Floyd-Warshall: caminhos mínimos entre todos os pares
- Tempo de atraso da rede e reconstrução de caminhos