Dijkstra com uma Heap
Encontre caminhos mínimos gulosos em arestas não negativas.
Dijkstra com uma Heap é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O problema do caminho mínimo
Você quer a rota de menor custo de um nó até todos os outros nós. O Dijkstra resolve isso quando o peso de cada aresta é zero ou positivo.
A ideia gulosa
O Dijkstra é guloso: ele sempre expande o nó não visitado com a menor distância conhecida, confiando que essa distância é definitiva.
Por que usar um montículo mínimo
Para obter rapidamente o nó mais próximo, você precisa de um montículo mínimo. Ele fornece a menor distância em tempo log n, em vez de exigir uma varredura lenta.
import heapqComece com as distâncias
Defina todas as distâncias como infinito e depois defina a origem como zero. Os nós não alcançados simplesmente permanecem em infinito para sempre.
dist = [float('inf')] * n
dist[src] = 0Inicialize o montículo
Insira a origem como uma tupla de (distância, nó). Colocar a distância primeiro permite que o montículo ordene as entradas automaticamente pelo custo.
pq = [(0, src)]Remova o nó mais próximo
Em cada iteração, remova o menor (d, u). Essa d é a menor distância até u, então o processamento desse nó termina assim que ele é removido.
d, u = heapq.heappop(pq)Ignore entradas obsoletas
Um nó pode permanecer no montículo com uma distância antiga e maior. Ignore-o quando d for maior que a distância armazenada.
if d > dist[u]:
continueRelaxe os vizinhos
Relaxamento significa tentar melhorar a distância até um vizinho: se passar por u for mais barato, atualize a distância dele e insira-o.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))O truque da remoção preguiçosa
Os montículos do Python não podem atualizar uma chave, então você insere duplicatas e ignora as obsoletas. Esse estilo preguiçoso mantém o código curto e rápido.
O tempo de execução
Com um montículo binário, o Dijkstra é executado em O((V + E) log V). Isso lida facilmente com grafos que têm centenas de milhares de arestas.
Fique atento aos pesos das arestas
O Dijkstra falha com arestas negativas, pois uma distância removida pode não ser definitiva. Nesses casos, use Bellman-Ford.
Verificação rápida
Você remove (d, u), mas d é maior que dist[u]. O que deve fazer?
Revisão: Dijkstra com um montículo
Você inicializa as distâncias, insere (dist, nó), remove o nó mais próximo, ignora remoções obsoletas e relaxa os vizinhos. Esse é o Dijkstra em O((V+E) log V). 🚀
Perguntas Frequentes
A aula “Dijkstra com uma Heap” é grátis?
Sim — o texto completo de “Dijkstra com uma Heap” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Dijkstra com uma Heap”?
Encontre caminhos mínimos gulosos em arestas não negativas. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Dijkstra com uma Heap”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Dijkstra com uma Heap
- BFS 0-1 com uma Deque
- Bellman-Ford e Arestas Negativas
- Floyd-Warshall para Todos os Pares