Pular para o conteúdo
</> Entendendo Algoritmos

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