Algoritmo de Dijkstra
Encontra o caminho de menor custo em um grafo com pesos nas arestas. A cada passo, escolhe o nó mais barato ainda não processado e atualiza o custo dos vizinhos. Não funciona com pesos negativos.
O caminho com menos arestas (inicio → a → fim) não é o mais barato: veja como o algoritmo descobre isso.
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 };
}