Algoritmo de Dijkstra
Matemática Computacional
Aviso Importante
Conteúdo
Encontrando o Caminho Mais Curto
Imagine que você precisa viajar de Dublin a Cork. Existem muitas rotas possíveis — algumas mais rápidas, algumas mais curtas, algumas mais econômicas em combustível. Este é um problema de busca de caminhos: dada uma rede de locais conectados por estradas, encontre a "melhor" rota de um ponto a outro. "Melhor" pode significar menor tempo, menor distância, maior largura de banda ou menor custo — todos esses são problemas de otimização.
Podemos modelar essas redes como grafos ponderados: locais se tornam nós (também chamados de vértices), estradas se tornam arestas, e cada aresta tem um peso — um número representando seu custo (distância, tempo, etc.). Um algoritmo é simplesmente uma série de instruções passo a passo para resolver um problema. O Algoritmo de Dijkstra (pronuncia-se "Dike-stra", em homenagem ao cientista da computação holandês Edsger Dijkstra) é um dos algoritmos mais famosos para encontrar o caminho mais curto em um grafo ponderado.
O objetivo é simples: encontrar uma sequência de nós conectando um nó de origem a um nó de destino que tenha o menor peso combinado das arestas. A abordagem de Dijkstra funciona explorando a partir do nó de origem, sempre escolhendo o vizinho não visitado mais próximo primeiro, e gradualmente construindo uma tabela de menores distâncias conhecidas. Quando ele alcança o destino, garante que o caminho é ótimo.
Por Que Precisamos de um Algoritmo?
A abordagem de força bruta não escala
Tente todos os caminhos possíveis de A até H, calcule o custo total de cada um e escolha o mais curto.
| 7 nodes | Centenas de caminhos |
| 100 nodes | Milhões de caminhos |
| 1,000 nodes | Mais caminhos do que átomos no universo |
Visite nós de forma inteligente — sempre escolha o nó não visitado mais próximo. Cada nó é visitado no máximo uma vez.
| 7 nodes | 7 passos |
| 100 nodes | ~100 passos |
| 1,000 nodes | ~1.000 passos |
Grafo Ponderado
O grafo que usaremos para rastrear o algoritmo de Dijkstra
Cada número em uma aresta representa o custo de viajar entre dois nós
O Algoritmo
Quatro passos para encontrar o caminho mais curto
Passo 0 — Começar no Nó A
Inicializar distâncias e começar
Passo 1 — Visitar o Nó C (custo 1)
C tem a menor distância na fila
Passo 2 — Visitar o Nó B (custo 2)
B tem a menor distância entre os nós não visitados
Passo 3 — Visitar o Nó D (custo 3)
Os vizinhos de D já foram visitados — sem atualizações
Passos 4 e 5 — Visitar E (custo 5), depois F (custo 7)
Chegando mais perto de H
Resultado — Caminho Mais Curto Encontrado!
A → C → F → H com custo total 9
Exemplo Resolvido 2 — Um Grafo Maior
Encontrando o caminho mais curto de S a T em um grafo de 7 nós
Exemplo Resolvido 2 — Passo a Passo Animado
Veja Dijkstra encontrar o caminho de S a T
Exemplo Resolvido 2 — Passo a Passo em Colunas
Colunas passo a passo de S a T
Exemplo Resolvido 3 — Encontrando Todos os Caminhos Mais Curtos
Às vezes a jornada importa mais do que o destino
Exemplo Resolvido 3 — Execução Completa de Dijkstra
Encontrando os caminhos mais curtos de P para todos os nós
| Destination | Shortest Distance | Path |
|---|---|---|
| Q | 1 | P → Q |
| R | 3 | P → Q → R |
| S | 6 | P → Q → R → S |
| T | 8 | P → Q → R → T |
| U | 7 | P → Q → R → S → U |
Exemplo Resolvido 3 — Passo a Passo em Colunas
Colunas passo a passo de P para todos os nós
Passo a Passo Detalhado
Executando Dijkstra de A a H — seguindo o algoritmo
Dijkstra vs A* — Comparação em Grade
Mesmo mapa, mesmo custo — mas veja quantos nós cada algoritmo visita
A* visitou 90 nós. Dijkstra visitou 555 — mais de 6 vezes mais. Vídeo de Kevin Wang.
A* visitou 90 nós. Dijkstra visitou 555 — mais de 6 vezes mais. Vídeo de Kevin Wang.
Dijkstra vs A* — Comparação no Mundo Real
Veja Dijkstra explorar cada rua de Roma antes de encontrar o caminho
Dijkstra levou 21:04 para encontrar o caminho. A* encontrou o mesmo caminho em apenas 02:03. Vídeo de Anthony Madorsky.
Dijkstra levou 21:04 para encontrar o caminho. A* encontrou o mesmo caminho em apenas 02:03. Vídeo de Anthony Madorsky.
Dijkstra vs A* — Entendendo a Diferença
Dois algoritmos, um objetivo — mas estratégias muito diferentes
- •Explores nodes in ALL directions equally
- •Guaranteed to find the shortest path
- •No knowledge of where the target is
- •Like a ripple spreading in a pond
- •Visits many unnecessary nodes
- •Explores towards the target first
- •Also guaranteed shortest path (with admissible heuristic)
- •Uses a heuristic — estimated distance to target
- •Like following a compass towards your destination
- •Visits far fewer nodes
A* adds one extra piece of information: an estimate of how far each node is from the target. Instead of picking the node with the smallest distance from start (like Dijkstra), A* picks the node with the smallest distance from start + estimated distance to target. This simple addition dramatically reduces the number of nodes explored.
| Feature | Dijkstra | A* |
|---|---|---|
| Uses heuristic? | No | Yes |
| Finds shortest path? | Always | Yes (with admissible heuristic) |
| Speed | Slower (explores everything) | Faster (focused search) |
| Memory usage | Higher | Lower |
| Best for | All shortest paths from one source | Single source to single target |
| Used in | Network routing, database queries | GPS navigation, video games |
Aplicações no Mundo Real
Onde algoritmos de caminho mais curto impulsionam nosso dia a dia
Every time you ask Google Maps or Apple Maps for directions, a variant of Dijkstra’s algorithm runs on millions of road segments. The edges are roads, weights are travel times (updated in real-time with traffic data), and the algorithm finds the fastest route. Modern GPS uses A* with geographical distance as the heuristic.
When you send a message on WhatsApp, it travels through multiple routers to reach its destination. Protocols like OSPF (Open Shortest Path First) use Dijkstra’s algorithm to find the fastest path through the network. Each router is a node, each connection is an edge weighted by latency or bandwidth.
Em jogos como Age of Empires, Civilization ou qualquer jogo de estratégia, unidades precisam navegar ao redor de obstáculos para alcançar seu destino. A* é o algoritmo padrão de busca de caminhos no desenvolvimento de jogos. Ele é executado milhares de vezes por segundo para mover personagens, inimigos e NPCs pelo mapa.
LinkedIn’s ‘degrees of connection’ and Facebook’s ‘People You May Know’ use graph algorithms to find short paths between users. The ‘six degrees of separation’ concept is essentially a shortest path problem on a social graph with billions of nodes.
Algoritmo de Dijkstra em Java
Usando uma fila de prioridade para encontrar o caminho mais curto
import java.util.*; public class DijkstraAlgorithm { // Find shortest distances from start to all nodes public static int[] dijkstra(int[][] graph, int start) { int n = graph.length; int[] distances = new int[n]; boolean[] visited = new boolean[n]; // Initialise all distances to "infinity" Arrays.fill(distances, Integer.MAX_VALUE); distances[start] = 0; // Priority queue: {distance, node} PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); queue.offer(new int[]{0, start}); while (!queue.isEmpty()) { int[] current = queue.poll(); int dist = current[0], node = current[1]; if (visited[node]) continue; visited[node] = true; // Check all neighbours for (int next = 0; next < n; next++) { if (graph[node][next] > 0 && !visited[next]) { int newDist = dist + graph[node][next]; if (newDist < distances[next]) { distances[next] = newDist; queue.offer(new int[]{newDist, next}); } } } } return distances; } }
public class Main { public static void main(String[] args) { // Adjacency matrix — 0 means no direct connection // A B C D E F H int[][] graph = { {0, 2, 1, 0, 0, 0, 0}, // A {2, 0, 0, 1, 3, 0, 0}, // B {1, 0, 0, 3, 0, 6, 0}, // C {0, 1, 3, 0, 0, 0, 0}, // D {0, 3, 0, 0, 0, 5, 0}, // E {0, 0, 6, 0, 5, 0, 2}, // F {0, 0, 0, 0, 0, 2, 0} // H }; String[] nodes = {"A","B","C","D","E","F","H"}; int[] distances = DijkstraAlgorithm.dijkstra(graph, 0); // Print shortest distances from A for (int i = 0; i < nodes.length; i++) { System.out.println("A → " + nodes[i] + " = " + distances[i]); } // Output: A → H = 9 } }
Referência Rápida
| Conceito | Notação | Significado |
|---|---|---|
| Nó (Vértice) | A, B, C... | Um ponto/local no grafo |
| Aresta | A—B | Uma conexão entre dois nós |
| Peso | w(A,B) = 3 | O custo de percorrer uma aresta |
| Grafo Ponderado | G(V, E) | Um grafo onde cada aresta tem um peso |
| Matriz de Adjacência | M[i][j] | Uma tabela armazenando os pesos das arestas entre todos os pares de nós |
| Tabela de Distâncias | d[v] | Rastreia a menor distância conhecida para cada nó |
| Caminho Mais Curto | A → C → F → H | A sequência de nós com menor peso total |
| Fila de Prioridade | min-heap | Seleciona o nó não visitado com a menor distância |
Exercícios Práticos
Teste seu entendimento do Algoritmo de Dijkstra
Qual é o custo total?
Mostre a tabela de distâncias após cada passo e identifique o caminho mais curto.
Encontre o caminho mais curto de A a E. Mostre seu raciocínio em cada passo.
a) Execute Dijkstra a partir de W para encontrar a menor distância até cada loja.
b) Qual é o caminho mais curto de W a S3?
c) Se a estrada W–S2 estiver fechada para obras, qual é o novo caminho mais curto de W a S3?
int[][] graph = {
{0, 6, 0, 1, 0},
{6, 0, 5, 2, 2},
{0, 5, 0, 0, 5},
{1, 2, 0, 0, 1},
{0, 2, 5, 1, 0}
};a) Qual distância Dijkstra reporta como a mais curta de A a C?
b) Qual é a distância mais curta REAL?
c) Por que Dijkstra falha?
d) Cite um algoritmo que lida com pesos negativos.
Mostre seu raciocínio passo a passo.
Mostre cada passo do algoritmo e identifique o caminho mais curto.
Arestas: S–A(2), S–B(5), A–C(4), A–E(7), B–D(2), B–E(1), C–T(3), D–T(4), E–C(1), E–D(3). Mostre seu raciocínio completo.
Arestas: R1–R2(3), R1–R3(6), R2–R4(2), R2–R5(5), R3–R5(3), R3–R6(1), R4–R7(4), R5–R7(2), R5–R6(2), R6–R8(5), R7–R8(1). Mostre a tabela de distâncias completa em cada passo.
Respostas
| A | B | C | |
|---|---|---|---|
| A | 0 | 3 | 5 |
| B | 3 | 0 | 1 |
| C | 5 | 1 | 0 |
Parte a) Dijkstra a partir de W:
| Step | Current | W | S1 | S2 | S3 | S4 |
|---|---|---|---|---|---|---|
| 0 | W | 0 | 10 | 5 | ∞ | ∞ |
| 1 | S2 | 0 | 8 | 5 | 13 | 7 |
| 2 | S4 | 0 | 8 | 5 | 11 | 7 |
| 3 | S1 | 0 | 8 | 5 | 9 | 7 |
| 4 | S3 | 0 | 8 | 5 | 9 | 7 |
Menores distâncias: S1=8, S2=5, S3=9, S4=7
Parte b) Caminho mais curto de W a S3:
W → S2 → S1 → S3, cost = 5 + 3 + 1 = 9
Parte c) W–S2 fechada:
Sem a aresta W–S2, o único caminho até S1 é direto (custo 10). Depois S1→S3 = 1. Então W → S1 → S3, custo = 10 + 1 = 11.
| Step | Current | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 6 | ∞ | 1 | ∞ |
| 1 | 3 | 0 | 3 | ∞ | 1 | 2 |
| 2 | 4 | 0 | 3 | 7 | 1 | 2 |
Caminho mais curto: 0 → 3 → 4, custo = 2 (1 + 1). A matriz mostra que do nó 0 ao nó 3 o peso é 1, e do nó 3 ao nó 4 o peso é 1.
b) O caminho mais curto real é A→B→C = 5 + (−10) = −5.
c) Dijkstra falha porque finaliza C com distância 2 antes de descobrir o caminho mais barato por B. Uma vez que um nó é marcado como visitado, ele nunca é reconsiderado — a suposição gulosa ("a menor distância é final") quebra quando existem pesos negativos, porque somar um peso negativo pode tornar um caminho mais longo mais curto.
d) O algoritmo de Bellman-Ford lida com pesos negativos relaxando TODAS as arestas V−1 vezes, garantindo que todos os caminhos mais curtos sejam encontrados.
b) Menor real: A→B→C = 1 + (−5) = −4.
c) Dijkstra marca C como visitado com distância 4 antes de descobrir o caminho por B. Uma vez visitados, nós nunca são reconsiderados — esta é a suposição fundamental que quebra com pesos negativos.
d) O algoritmo de Bellman-Ford lida com pesos negativos relaxando todas as arestas V−1 vezes, garantindo que todos os caminhos mais curtos sejam encontrados.
Referências
Fontes utilizadas na elaboração deste material
Bons estudos!
Algoritmos são a base da resolução eficiente de problemas em computação