Dijkstra: trocando um livro por um piano
O segundo exemplo do capítulo 7: você quer trocar um livro por um piano, passando por uma série de trocas, e cada troca exige pagar uma diferença em dinheiro. O caminho mais barato no grafo é a série de trocas mais econômica. O Dijkstra serve para qualquer custo, não só distância ou tempo, desde que não seja negativo.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
function dijkstra(grafo, inicio, fim) {
const custos = {};
const pais = {};
for (const no in grafo) {
custos[no] = Infinity;
pais[no] = null;
}
custos[inicio] = 0;
const processados = new Set();
while (true) {
// acha o nó mais barato ainda não processado
let atual = null;
for (const no in custos) {
if (processados.has(no) || custos[no] === Infinity) continue;
if (atual === null || custos[no] < custos[atual]) atual = no;
}
if (atual === null) break;
// atualiza o custo dos vizinhos, se passar por aqui for mais barato
for (const [vizinho, peso] of Object.entries(grafo[atual])) {
if (custos[atual] + peso < custos[vizinho]) {
custos[vizinho] = custos[atual] + peso;
pais[vizinho] = atual;
}
}
processados.add(atual);
}
if (custos[fim] === Infinity) return null; // sem caminho
const caminho = [];
for (let no = fim; no !== null; no = pais[no]) caminho.unshift(no);
return { custo: custos[fim], caminho };
}