Algoritmo que calcula a menor distância entre um vértice de origem e todos os outros em grafos com pesos positivos.
Dijkstra resolve um problema que aparece em todo lugar: qual o caminho mais curto entre dois pontos? GPS, roteamento de pacotes, jogos — todos usam alguma variante dele. A sacada é simples: se você sempre processar o vértice mais próximo da origem primeiro, a distância dele nunca vai mudar. Por quê? Porque qualquer outro caminho passaria por vértices mais distantes, e com pesos positivos, isso só aumentaria o custo. É um algoritmo guloso que funciona. A escolha local (processar o mais próximo) é globalmente ótima.
“A mágica está na fila de prioridade. Sem ela, você teria que varrer todos os vértices para achar o mínimo — O(V²) em vez de O(log V).”
Cada vértice entra e sai da fila uma vez (V operações de log V). Cada aresta pode causar uma atualização na fila (E operações de log V).
Com binary heap, inserção e extração custam O(log V). Temos no máximo V extrações e E atualizações.
Arrays de distâncias e predecessores, mais a fila que pode ter no máximo V elementos.
A complexidade não muda com a estrutura do grafo.
Mesmo no pior caso, cada aresta é processada uma vez.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Dijkstra(atual) | O((V+E) log V) | O(V) | Grafos com pesos positivos |
| Bellman-Ford | O(V × E) | O(V) | Grafos com pesos negativos |
| Floyd-Warshall | O(V³) | O(V²) | Distância entre todos os pares |
| BFS | O(V + E) | O(V) | Grafos sem peso (arestas com custo 1) |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1import heapqImports2from collections import defaultdictImports3 4 5def dijkstra(graph, start):Definição6 distances = {node: float('inf') for node in graph}Inicialização7 distances[start] = 0Inicialização8 9 pq = [(0, start)]Fila de Prioridade10 visited = set()11 12 while pq:Loop Principal13 current_dist, current = heapq.heappop(pq)Extrair Mínimo14 15 if current in visited:Pular Visitado16 continuePular Visitado17 visited.add(current)18 19 for neighbor, weight in graph[current]:Relaxamento20 distance = current_dist + weightAtualizar Distância21 22 if distance < distances[neighbor]:Relaxamento23 distances[neighbor] = distanceAtualizar Distância24 heapq.heappush(pq, (distance, neighbor))Fila de Prioridade25 26 return distancesRetorno27