Bellman-Ford e Arestas Negativas
Trate valores negativos e detecte ciclos.
Bellman-Ford e Arestas Negativas é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Quando o Dijkstra falha
O Dijkstra confia que uma distância removida é definitiva, mas uma aresta negativa pode tornar um caminho mais barato depois. Por isso, ele falha.
Conheça Bellman-Ford
O Bellman-Ford lida com pesos de arestas negativos. Ele é mais lento que o Dijkstra, mas é robusto quando não se pode confiar na lógica gulosa.
A operação central
Ele relaxa repetidamente todas as arestas: se dist[u] mais o peso da aresta for menor que dist[v], atualize dist[v] para esse valor menor.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wQuantas rodadas
Um caminho mínimo usa no máximo V menos 1 arestas, então V-1 rodadas relaxando todas as arestas são suficientes para determinar todas as distâncias.
for _ in range(n - 1):
relax_all_edges()Inicialize as distâncias
Comece com todas as distâncias em infinito, exceto a origem, que deve receber zero, exatamente como no Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Uma passagem completa
Cada passagem percorre toda a lista de arestas uma vez e relaxa cada aresta. As melhorias se propagam para fora, um salto por passagem.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wPor que V-1 é suficiente
Após k passagens, todos os caminhos mínimos que usam k arestas estão corretos. Depois de V-1 passagens, todo caminho mínimo simples está concluído.
A passagem extra
Faça mais uma passagem. Se alguma distância ainda diminuir, algo continua ficando mais barato, o que indica um ciclo negativo.
Detectando ciclos negativos
Um ciclo negativo significa que não existe um caminho mínimo finito, pois você pode repetir o ciclo indefinidamente para reduzir o custo sem limite.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'O tempo de execução
Você relaxa E arestas ao longo de V passagens, então o Bellman-Ford é executado em O(V * E), o que é adequado para grafos pequenos ou médios.
Dijkstra ou Bellman-Ford
Escolha o Dijkstra para pesos não negativos e velocidade. Escolha Bellman-Ford quando houver pesos negativos ou quando for necessário detectar um ciclo negativo.
Verificação rápida
Depois de V-1 passagens, uma distância ainda diminui em mais uma passagem. O que isso significa?
Revisão: Bellman-Ford
Relaxe todas as arestas por V-1 passagens e faça mais uma para detectar ciclos negativos. Ele é O(V*E), mas funciona onde o Dijkstra não consegue. ✅
Perguntas Frequentes
A aula “Bellman-Ford e Arestas Negativas” é grátis?
Sim — o texto completo de “Bellman-Ford e Arestas Negativas” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Bellman-Ford e Arestas Negativas”?
Trate valores negativos e detecte ciclos. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 3 de 4.
Quanto tempo leva a aula “Bellman-Ford e Arestas Negativas”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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
- Dijkstra com uma Heap
- BFS 0-1 com uma Deque
- Bellman-Ford e Arestas Negativas
- Floyd-Warshall para Todos os Pares