Pular para o conteúdo
</> Entendendo Algoritmos

Bellman-Ford

O Dijkstra assume que, ao processar um nó, o custo dele já é o menor possível. Com pesos negativos (um desconto, um reembolso) isso deixa de ser verdade. O Bellman-Ford não faz essa suposição: relaxa todas as arestas várias vezes e, se ainda melhorar depois do limite, há um ciclo negativo.

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
function bellmanFord(nos, arestas, inicio) {
  const custos = {};
  for (const no of nos) custos[no] = no === inicio ? 0 : Infinity;

  // relaxa todas as arestas V - 1 vezes
  for (let rodada = 1; rodada < nos.length; rodada++) {
    for (const { de, para, peso } of arestas) {
      if (custos[de] + peso < custos[para]) {
        custos[para] = custos[de] + peso;
      }
    }
  }

  // uma rodada extra: se ainda melhora, existe um ciclo negativo
  const cicloNegativo = arestas.some(
    ({ de, para, peso }) => custos[de] + peso < custos[para],
  );

  return { custos, cicloNegativo };
}