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 };
}