Algoritmo de Dijkstra (Aulas 20 e 21)

Published

16/06/2026

Modified

26/05/2026

Parte 1: A Mecânica do Algoritmo (Aula 20)

1. O GPS dos Grafos

Se você abre o Google Maps e pede uma rota, ele usa uma variante do algoritmo de Edsger W. Dijkstra (1956). Diferente da BFS (que só serve para arestas de peso 1), o Dijkstra encontra o Caminho Mínimo em grafos onde as arestas têm pesos variados não-negativos.

Analogia da Água: Imagine que a água começa a fluir da origem. Ela percorre canos (arestas) de comprimentos diferentes. O algoritmo determina em que “momento” a água chega em cada cidade.

Restrição de Ouro: Funciona APENAS para grafos onde todos os pesos são não-negativos (\(w \ge 0\)).

Por que não usar BFS?

A Busca em Largura garante o menor número de arestas, mas ignora completamente os pesos. Se uma aresta direta custa 100 e um caminho alternativo por 2 arestas custa 25, a BFS escolheria o caminho direto (1 aresta) em vez do caminho mais barato (2 arestas, custo 25).

2. Conceito de Relaxamento

A base de todos os algoritmos de menor caminho é a operação de Relaxamento (Relaxation). Seja D[v] a melhor distância conhecida até agora da origem até v.

Imagine que conhecemos um caminho para \(v\) que custa \(10\). Descobrimos uma aresta \(u \to v\) com peso \(2\), e sabemos que chegamos em \(u\) com custo \(5\). Novo custo potencial via \(u\): \(D[u] + peso(u, v) = 5 + 2 = 7\). Como \(7 < 10\), nós relaxamos a aresta: atualizamos D[v] = 7 e dizemos que o pai de \(v\) agora é \(u\).

Relaxamento: se dist[u] + peso(u,v) < dist[v], atualizar dist[v] e pai[v].

Relaxamento: se dist[u] + peso(u,v) < dist[v], atualizar dist[v] e pai[v].

A Fórmula do Relaxamento

if (dist[u] + w(u,v) < dist[v])
    dist[v] = dist[u] + w(u,v)
    pai[v] = u

3. O Algoritmo Guloso

  1. Inicialização: dist[S] = 0, todos os outros dist[v] = ∞.
  2. Priority Queue: Coloque par (0, S) na fila.
  3. Enquanto a PQ não estiver vazia:
    • Extraia o vértice \(u\) com a menor distância atual.
    • Se essa distância for maior que dist[u] (info obsoleta), ignore (Lazy Deletion).
    • Para cada vizinho \(v\) de \(u\), tente relaxar a aresta \((u,v)\).
    • Se relaxar, empurre (novo_dist, v) para a PQ.

Fila de prioridade: sempre extrair o vértice com menor distância atual.

Fila de prioridade: sempre extrair o vértice com menor distância atual.

Por que Guloso?

O algoritmo assume que, se extraímos \(u\) da fila com distância \(X\), não existe nenhum outro caminho no mundo que chegue em \(u\) com custo menor que \(X\). Isso é verdade porque arestas negativas não existem — qualquer caminho alternativo passando por outros nós da fila só pode ter custo \(\ge X\).

4. Trace Animado (Exemplo Passo a Passo)

Considere o grafo com 4 vértices e origem = 0:

        0 --(4)--> 1
        |          |
       (1)        (1)
        |          |
        v          v
        2 --(2)--> 1
        2 --(5)--> 3

Arestas: 0→1 (peso 4), 0→2 (peso 1), 2→1 (peso 2), 1→3 (peso 1), 2→3 (peso 5).

Nó Extraído Vizinhos (Relaxamento) Fila (PQ)
— — (0, custo:0)
Visita 0 1 (custo:4), 2 (custo:1) (2, c:1), (1, c:4)
Visita 2 1 (1+2=3), 3 (1+5=6) (1, c:3), (1, c:4), (3, c:6)
Visita 1 3 (3+1=4) (1, c:4), (3, c:4), (3, c:6)
Ignora 1! (já dist[1]=3 < 4) (3, c:4), (3, c:6)
Visita 3 nenhum (3, c:6)
Ignora 3! (já dist[3]=4 < 6) vazia

Resultado Final: dist[0]=0, dist[1]=3, dist[2]=1, dist[3]=4

5. A Árvore de Caminhos Mínimos

Ao final da execução, se seguirmos de trás para frente usando o vetor de pais, formamos a Árvore de Caminhos Mínimos (Shortest Path Tree).

Para reconstruir o caminho até o vértice 3: \(3 \leftarrow 1 \leftarrow 2 \leftarrow 0\). Logo, a rota é \(0 \rightarrow 2 \rightarrow 1 \rightarrow 3\) com custo total 4.

Caminho mínimo da origem a cada vértice; setas vermelhas representam os ponteiros de ‘pai’.

Caminho mínimo da origem a cada vértice; setas vermelhas representam os ponteiros de ‘pai’.

Parte 2: Implementação e Casos Especiais (Aula 21)

6. Implementação em Java

Atenção: A PriorityQueue do Java guarda objetos. Devemos criar uma classe ou usar array.

6.1 Estrutura Node

import java.util.*;

class Node implements Comparable<Node> {
    int id;
    int distance;
    
    public Node(int id, int dist) {
        this.id = id;
        this.distance = dist;
    }
    
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance); // Min-Heap
    }
}

6.2 O Algoritmo

public static int[] dijkstra(int V, List<List<Edge>> adj, int startNode) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE); // Tudo infinito no início
    dist[startNode] = 0;
    
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(startNode, 0));
    
    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int u = current.id;
        
        // Lazy Deletion: Se já achamos um caminho melhor pra `u` e
        // este nó na fila ficou obsoleto, apenas ignore.
        if (current.distance > dist[u]) continue; 
        
        // Relaxa vizinhos
        for (Edge e : adj.get(u)) {
            if (dist[u] + e.peso < dist[e.destino]) {
                dist[e.destino] = dist[u] + e.peso;
                // Adiciona o novo caminho relaxado na fila
                pq.add(new Node(e.destino, dist[e.destino]));
            }
        }
    }
    return dist;
}

6.3 Reconstrução do Caminho

Para reconstruir o caminho, basta manter um array pai[] e atualizá-lo durante o relaxamento:

// Durante o relaxamento:
if (dist[u] + e.peso < dist[e.destino]) {
    dist[e.destino] = dist[u] + e.peso;
    pai[e.destino] = u;  // Lembra de onde veio
    pq.add(new Node(e.destino, dist[e.destino]));
}

// Para reconstruir o caminho até o destino:
List<Integer> path = new ArrayList<>();
for (int v = destino; v != -1; v = pai[v]) {
    path.add(v);
}
Collections.reverse(path);

7. O Calcanhar de Aquiles: Pesos Negativos

O que acontece se uma aresta tiver custo \(-10\)?

A Quebra do Paradigma Guloso

O Dijkstra sela a distância de um vértice quando o tira da fila, assumindo que nenhum caminho futuro será mais barato. Arestas negativas permitem “voltar no tempo” e criar um atalho milagroso, burlando a premissa fundamental do algoritmo e gerando respostas erradas.

Ciclo Negativo

Pior ainda: se as arestas formarem um ciclo com soma total negativa, o algoritmo vai girar nele reduzindo o custo infinitamente rumo ao \(-\infty\).

A Solução Definitiva

Para grafos com pesos negativos ou para detectar ciclos negativos de forma segura, usamos outro algoritmo clássico: Bellman-Ford com complexidade \(O(V \times E)\).

8. Complexidade Computacional

Implementação Complexidade
Com Binary Heap (PriorityQueue Java) \(O((V + E) \log V) \approx O(E \log V)\)
Sem Heap (Busca Linear / Matriz) \(O(V^2)\)
Com Fibonacci Heap \(O(E + V \log V)\) (teórico)
  • A versão com Binary Heap é perfeita para quase qualquer cenário real.
  • A versão sem Heap (\(O(V^2)\)) é surpreendentemente mais rápida apenas se o grafo for extremamente denso (\(E \approx V^2\)).
  • A Fibonacci Heap tem o limite teórico ótimo, mas constante muito alta na prática.

9. Aplicações no Mundo Real

  • Protocolos de Roteamento de Internet: OSPF e IS-IS calculam a árvore de rotas mais curtas nas entranhas da Internet usando o Dijkstra.
  • Pathfinding em Mapas e Games: O motor de rotas do Google Maps e movimentos de I.A. em jogos usam o A* (A-Star), que é matematicamente um Dijkstra guiado por uma Heurística.
  • Logística e Transporte: Otimização de rotas de entrega e distribuição.
  • Telecomunicações: Roteamento de chamadas em redes telefônicas.

10. Exercícios

10.1. Exercícios Conceituais

  1. Por que Dijkstra não funciona com arestas de peso negativo? Dê um contraexemplo.
  2. Explique o conceito de “lazy deletion” na implementação de Dijkstra com Priority Queue. Por que é necessário?
  3. Compare Dijkstra com BFS. Quando BFS é suficiente e quando precisamos de Dijkstra?

10.2. Exercícios Analíticos

  1. Simule Dijkstra passo a passo no grafo:

        0 --(1)--> 1 --(3)--> 3
    |          |
   (4)        (2)
    |          |
    v          v
    2 --(1)--> 4

    A partir do vértice 0, mostre a fila de prioridade e distâncias em cada iteração.

  2. Para um grafo completo \(K_n\) com pesos unitários, compare o número de operações de Dijkstra vs BFS. Qual é mais eficiente?

  3. Analise a complexidade de Dijkstra quando:

    • Usamos Binary Heap (PriorityQueue padrão).
    • Usamos array simples para a fila (sem heap).

    Quando cada implementação é preferível?

10.3. Exercícios de Programação

  1. Implemente Dijkstra completo com:
    • Cálculo de distâncias mínimas.
    • Reconstrução de caminhos usando array de pais.
    • Suporte a grafos direcionados e não direcionados.
  2. Compare o desempenho de Dijkstra usando Binary Heap vs array simples em grafos densos e esparsos.
  3. Resolva problemas de juiz online relacionados a caminhos mínimos, como:
    • Caminho mínimo entre dois vértices específicos.
    • Caminhos mínimos de um vértice para todos os outros.
    • Problemas de roteamento em redes.
Back to top