Algoritmo de Dijkstra
Encontra o caminho mais curto em grafos ponderados — escolhendo sempre o nó mais barato ainda não finalizado.
O(V+E)O(V+E)Como Funciona
Passo a passo do algoritmo
Inicialização
Defina dist[origem]=0 e dist[todos os demais]=∞. Insira (origem, 0) na fila de prioridade (min-heap). Nenhum nó foi finalizado ainda.
dist[s]=0; dist[v]=∞ para v≠s; fila=[(s,0)]Extrair o mínimo
Retire da fila o nó u com menor distância acumulada. Esse nó tem sua distância definitivamente estabelecida — nunca será melhorada. Isso é a garantia central do algoritmo.
u = fila.extrair_min()Relaxamento de arestas
Para cada vizinho v de u com peso w: se dist[u]+w < dist[v], atualize dist[v], registre prev[v]=u e insira (v, nova_dist) na fila. Caso contrário, ignore.
para v em vizinhos(u): se dist[u]+w < dist[v]: dist[v]=dist[u]+w; prev[v]=uGarantia de correção
Todo nó extraído da fila tem distância definitivamente mínima. Isso ocorre porque todos os pesos são positivos: nenhum caminho mais longo pode ser mais barato que o atual mínimo extraído.
invariante: quando u é extraído, dist[u] é ótimaReconstrução do caminho
Para obter o caminho até um destino d, siga os ponteiros prev[]: d → prev[d] → prev[prev[d]] → … → origem. Inverta a sequência para obter o caminho na direção correta.
caminho = []; cur=d; enquanto prev[cur]≠null: caminho.prepend(cur); cur=prev[cur]Implementação
Código comentado em JavaScript e Python
function dijkstra(grafo, inicio) {
const dist = {};
const prev = {};
const visitados = new Set();
// Inicialização
for (const no of Object.keys(grafo)) {
dist[no] = Infinity;
prev[no] = null;
}
dist[inicio] = 0;
// Fila de prioridade simples (array ordenado)
const fila = [{ no: inicio, dist: 0 }];
while (fila.length > 0) {
// Extrair mínimo
fila.sort((a, b) => a.dist - b.dist);
const { no: u } = fila.shift();
if (visitados.has(u)) continue; // entrada obsoleta
visitados.add(u);
for (const { vizinho, peso } of grafo[u]) {
const novaDist = dist[u] + peso;
if (novaDist < dist[vizinho]) {
dist[vizinho] = novaDist;
prev[vizinho] = u;
fila.push({ no: vizinho, dist: novaDist });
}
}
}
return { dist, prev };
}
// Reconstruir caminho até destino
function reconstruirCaminho(prev, destino) {
const caminho = [];
let cur = destino;
while (cur !== null) {
caminho.unshift(cur);
cur = prev[cur];
}
return caminho;
}
// Exemplo de uso
const grafo = {
1: [{ vizinho: 2, peso: 4 }, { vizinho: 3, peso: 2 }],
2: [{ vizinho: 1, peso: 4 }, { vizinho: 4, peso: 5 }, { vizinho: 6, peso: 10 }],
3: [{ vizinho: 1, peso: 2 }, { vizinho: 5, peso: 3 }, { vizinho: 6, peso: 8 }],
4: [{ vizinho: 2, peso: 5 }, { vizinho: 6, peso: 2 }],
5: [{ vizinho: 3, peso: 3 }, { vizinho: 6, peso: 1 }],
6: [{ vizinho: 2, peso: 10 }, { vizinho: 3, peso: 8 }, { vizinho: 4, peso: 2 }, { vizinho: 5, peso: 1 }]
};
const { dist, prev } = dijkstra(grafo, 1);
console.log('dist[6]:', dist[6]); // 6
console.log('caminho:', reconstruirCaminho(prev, 6)); // [1, 3, 5, 6]Playground
Visualize o Dijkstra encontrando caminhos mais curtos ponderados
| Nó | Dist | Via |
|---|---|---|
| 1 | 0 | — |
| 2 | ∞ | — |
| 3 | ∞ | — |
| 4 | ∞ | — |
| 5 | ∞ | — |
| 6 | ∞ | — |
Quando Usar
Cenários ideais para este algoritmo
GPS e navegação
Aplicativos como Google Maps e Waze usam Dijkstra (e variantes como A*) para encontrar a rota de menor tempo entre dois pontos no mapa viário.
Roteamento de rede
O protocolo OSPF (usado em roteadores da internet) aplica Dijkstra para calcular as rotas de menor custo entre roteadores em uma sub-rede.
Pathfinding em jogos
Jogos com mapas em grade ponderada (diferentes custos de terreno) usam Dijkstra ou A* para mover personagens e NPCs pelo caminho mais eficiente.
Redes elétricas
Planejamento de transmissão de energia: encontrar o caminho de menor resistência (e menor perda) entre a usina geradora e os consumidores finais.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Com min-heap | O((V+E) log V) |
| Sem heap (ingênuo) | O(V²) |
| Com heap de Fibonacci | O(E + V log V) |