Algoritmo Bellman-Ford
Última atualização
O Bellman-Ford encontra o caminho mais curto de um nó de origem para todos os outros nós e, ao contrário de Dijkstra, funciona mesmo quando alguns pesos de aresta são negativos. Ele funciona por relaxamento por força bruta: percorre repetidamente cada aresta e, se passar por ela dá uma distância menor, atualiza a distância do nó de destino. Pressione reproduzir acima para ver as distâncias tentativas caírem passagem a passagem.
Após V - 1 passagens sobre todas as arestas, cada caminho mais curto (que pode ter no máximo V - 1 arestas) foi encontrado. Isso o torna O(V · E) - mais lento que Dijkstra, mas lida com pesos negativos e pode detectar um ciclo de peso negativo (se uma V-ésima passagem ainda relaxa uma aresta, não existe caminho mais curto).
Complexidade de tempo e espaço
| Medida | Complexidade | Notas |
|---|---|---|
| Tempo | O(V · E) | V − 1 passagens sobre todas as E arestas |
| Espaço | O(V) | Uma distância por nó |
| Pesos negativos | Suportados | Sua vantagem chave sobre Dijkstra |
| Ciclos negativos | Detectáveis | Uma V-ésima passagem que relaxa indica um |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Defina a distância da origem como 0 e todas as outras como infinito. |
| 2 | Repita o próximo passo V − 1 vezes. |
| 3 | Para cada aresta (u → v, w), verifique se dist[u] + w < dist[v]. |
| 4 | Se sim, relaxe-a: defina dist[v] = dist[u] + w. |
| 5 | Pare antes se uma passagem completa não mudar nada. |
Exemplo resolvido
Origem S em 4 nós S, A, B, C com arestas S→A (4), S→B (5), A→C (3), B→A (-3), relaxadas nessa ordem. As distâncias começam em S=0 e tudo o mais em ∞:
| Passagem | Distâncias [S, A, B, C] | Ação |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | A distância da origem é 0, todas as outras infinito. |
| 1 | [0, 2, 5, 7] | Relaxa S→A para 4, S→B para 5, A→C para 7, e então B→A baixa A para 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C agora melhora C para 2 + 3 = 5; nenhuma outra aresta relaxa. |
| 3 | [0, 2, 5, 5] | Nenhuma aresta relaxa, então as distâncias são finais: A custa 2 via S→B→A. |
Quando usar Bellman-Ford
| Use quando | Evite quando |
|---|---|
| Os pesos de aresta podem ser negativos. | Todos os pesos são não negativos (Dijkstra é mais rápido). |
| Você precisa detectar ciclos de peso negativo. | O grafo é enorme e denso - O(V · E) é lento demais. |
| O grafo é pequeno ou esparso. | Você só precisa de uma consulta origem-destino em um grafo grande. |
| Você precisa de uma base simples e fácil de implementar. | Os pesos são não negativos e a latência importa. |
Código de Bellman-Ford Algorithm
Uma implementação limpa e executável de Bellman-Ford Algorithm em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Bellman-Ford Algorithm em Python
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Código de Bellman-Ford Algorithm em JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Código de Bellman-Ford Algorithm em Java
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Código de Bellman-Ford Algorithm em C++
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Código de Bellman-Ford Algorithm em C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}Perguntas frequentes sobre Bellman-Ford
Qual é a complexidade de tempo do Bellman-Ford?
O Bellman-Ford roda em tempo
O(V · E): faz V - 1 passagens e cada passagem relaxa todas as E arestas. Isso é mais lento que o O((V + E) log V) de Dijkstra, que é o preço de suportar pesos de aresta negativos.Quando devo usar Bellman-Ford em vez de Dijkstra?
Use Bellman-Ford quando o grafo puder ter pesos de aresta negativos, ou quando você precisar detectar ciclos de peso negativo. Dijkstra é mais rápido, mas só é correto com pesos não negativos. Um uso real comum é a detecção de arbitragem em câmbio de moedas, onde ciclos negativos importam.
Como o Bellman-Ford detecta um ciclo negativo?
Após as
V - 1 passagens de relaxamento, todos os caminhos mais curtos estão finalizados se não existir ciclo negativo. Se mais uma passagem ainda puder relaxar uma aresta, então há um ciclo de peso negativo alcançável, e os caminhos mais curtos ficam indefinidos (você poderia repetir o laço infinitamente para reduzir o custo).Qual é a diferença entre Bellman-Ford e Floyd-Warshall?
O Bellman-Ford calcula os caminhos mais curtos a partir de uma única origem em
O(V · E), enquanto o Floyd-Warshall calcula os caminhos mais curtos entre todos os pares em O(V³). Em um grafo denso, rodar Bellman-Ford a partir de cada origem custa O(V² · E), então Floyd-Warshall costuma ser a melhor escolha quando você precisa de todos os pares. Ambos lidam com arestas negativas e podem sinalizar ciclos negativos.Por que o Bellman-Ford precisa de exatamente V - 1 passagens?
Qualquer caminho mais curto em um grafo sem ciclos negativos usa no máximo
V - 1 arestas, porque um caminho que visita mais de V nós precisa repetir um. Cada passagem garante que pelo menos mais uma aresta de cada caminho mais curto seja relaxada corretamente, então V - 1 passagens bastam para fixar todos. Um equívoco comum é achar que mais passagens melhoram o resultado - nunca melhoram, a menos que exista um ciclo negativo.O Bellman-Ford pode parar antes?
Sim. Se uma passagem completa sobre todas as arestas não relaxar nada, todas as distâncias já são ótimas e você pode parar antes de atingir as
V - 1 passagens. Essa otimização de saída antecipada costuma torná-lo muito mais rápido em grafos que convergem cedo, embora o limite de pior caso continue sendo O(V · E).Recursos relacionados
Mais visualizações
