Algoritmo de Dijkstra
Última atualização
O algoritmo de Dijkstra encontra o caminho mais curto de um nó de origem até todos os outros nós de um grafo com pesos de aresta não negativos. Ele mantém uma distância tentativa para cada nó, fixa repetidamente o nó não fixado com a menor distância tentativa e relaxa suas arestas, atualizando a distância de um vizinho sempre que uma rota mais curta através do nó atual é encontrada. Pressione reproduzir acima para ver as distâncias caírem à medida que cada nó é fixado.
A ideia central é gulosa: uma vez escolhido o nó não fixado mais próximo, sua distância é definitiva, porque qualquer outra rota até ele teria de passar por um nó que já está mais distante. Com uma fila de prioridade baseada em heap binário, Dijkstra é executado em tempo O((V + E) log V). Ele requer pesos não negativos: use Bellman-Ford se as arestas puderem ser negativas.
Complexidade de tempo e espaço
| Implementação | Complexidade | Notas |
|---|---|---|
| Heap binário | O((V + E) log V) | A escolha comum e prática |
| Varredura de array | O(V²) | Mais simples; adequado para grafos densos |
| Espaço | O(V) | Distâncias + fila de prioridade |
| Requer | Pesos não negativos | Arestas negativas quebram a escolha gulosa |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Defina a distância da origem como 0 e todas as outras como infinito. |
| 2 | Escolha o nó não fixado com a menor distância tentativa. |
| 3 | Marque-o como fixado: sua distância mais curta agora é definitiva. |
| 4 | Para cada vizinho, calcule distância-através-do-atual + peso da aresta. |
| 5 | Se for menor que a distância atual do vizinho, relaxe-a. |
| 6 | Repita até fixar todos os nós alcançáveis. |
Exemplo resolvido
Caminhos mais curtos a partir da origem A no grafo com arestas A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Passo | Fixar | Distâncias | Ação |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Inicialize: origem A=0, todos os outros infinito. |
| 1 | A (0) | B=4, C=1, D=∞ | Relaxa as arestas de A: define B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Através de C: B=1+2=3 supera 4; D=1+5=6. |
| 3 | B (3) | D=4 | Através de B: D=3+1=4 supera 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Fixa D; nada mais para relaxar. Concluído. |
Quando usar o algoritmo de Dijkstra
| Use quando | Evite quando |
|---|---|
| Todos os pesos de aresta são não negativos | Qualquer aresta pode ser negativa: use Bellman-Ford |
| Você precisa dos caminhos mais curtos de uma origem para todos os nós | Você precisa dos caminhos mais curtos entre todos os pares: Floyd-Warshall é mais simples |
| O grafo é ponderado e você quer distâncias exatas | O grafo não é ponderado: um BFS simples é mais rápido e simples |
| Você tem um bom heap ou fila de prioridade disponível | Você quer chegar rápido a um único destino com uma heurística: use A* |
Código de Dijkstra's Algorithm
Uma implementação limpa e executável de Dijkstra's Algorithm em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Dijkstra's Algorithm em Python
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Código de Dijkstra's Algorithm em JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Código de Dijkstra's Algorithm em Java
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Código de Dijkstra's Algorithm em C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Código de Dijkstra's Algorithm em C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Perguntas frequentes sobre o algoritmo de Dijkstra
Qual é a complexidade de tempo do algoritmo de Dijkstra?
Com uma fila de prioridade baseada em heap binário, ele roda em
O((V + E) log V). Uma versão simples que varre um array em busca do mínimo a cada passo é O(V²), que na verdade pode ser mais rápida em grafos densos. Ambas usam espaço O(V).Por que Dijkstra não funciona com pesos de aresta negativos?
Dijkstra pressupõe que, uma vez fixado o nó não fixado mais próximo, essa distância é definitiva. Uma aresta negativa poderia criar depois um caminho mais curto até um nó já fixado, quebrando essa suposição. Para grafos com pesos negativos, use o algoritmo de Bellman-Ford.
Qual é a diferença entre Dijkstra e BFS?
BFS encontra os caminhos mais curtos contando arestas (cada peso de aresta é efetivamente 1), usando uma fila simples. Dijkstra generaliza isso para grafos ponderados sempre expandindo o nó com a menor distância total, usando uma fila de prioridade. Em um grafo não ponderado, ambos produzem os mesmos caminhos.
Qual é a diferença entre Dijkstra e a busca A*?
A* é Dijkstra mais uma heurística que estima a distância restante até um destino, de modo que direciona a busca para esse objetivo em vez de se expandir uniformemente em todas as direções. Quando a heurística é zero, A* se reduz exatamente a Dijkstra. Use A* quando tiver um único destino e uma boa heurística admissível; use Dijkstra quando precisar de distâncias para todos os nós.
Quando devo usar Dijkstra em vez de Bellman-Ford?
Use Dijkstra sempre que todos os pesos de aresta forem não negativos: é mais rápido,
O((V + E) log V) contra O(V·E) do Bellman-Ford. Escolha Bellman-Ford apenas quando as arestas puderem ser negativas ou você precisar detectar ciclos negativos. Em grafos não negativos, Dijkstra é quase sempre a melhor escolha.Dijkstra pode revisitar um nó depois de fixá-lo?
Não: uma vez que um nó é fixado, sua distância é definitiva e nunca é relaxada novamente. Um erro comum nas implementações com heap é deixar entradas obsoletas na fila de prioridade após a distância de um nó melhorar; você deve ignorar um nó retirado se ele já estiver fixado (sua distância retirada excede a distância registrada). Esquecer essa verificação ainda dá respostas corretas, mas desperdiça trabalho.
Recursos relacionados
Mais visualizações
