Algoritmo de Dijkstra

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.

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\).

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.
    • Para cada vizinho \(v\) de \(u\), tente relaxar a aresta \((u,v)\).
    • Se relaxar, empurre (novo_dist, v) para a PQ.

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.

4. Implementação em Java

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

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);
    }
}

public class Dijkstra {
    
    public static int[] dijkstra(int V, List<List<Edge>> adj, int startNode) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        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;
            int d = current.distance;
            
            // Lazy Deletion: Se já achamos um caminho melhor antes, esse é lixo
            if (d > dist[u]) continue;
            
            // Explora vizinhos
            for (Edge e : adj.get(u)) {
                int v = e.destino;
                int peso = e.peso;
                
                // Relaxamento
                if (dist[u] + peso < dist[v]) {
                    dist[v] = dist[u] + peso;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }
}

5. Limitações e Complexidade

O Problema dos Pesos Negativos

Se houver uma aresta com peso \(-10\), o critério guloso falha. Podemos “voltar no tempo” e achar um caminho melhor depois de ter fechado um vértice. Pior ainda, se houver um Ciclo Negativo, podemos ficar girando nele e diminuindo o custo infinitamente (\(-\infty\)). Para pesos negativos, use Bellman-Ford.

Complexidade

  • Com Binary Heap (PriorityQueue padrão): \(O(E \log V)\).
  • Com Fibonacci Heap: \(O(E + V \log V)\) (Teórico, complexo demais para prática).
  • Array Simples: \(O(V^2)\) (Bom apenas para grafos muito densos).

Aplicações

  • Roteamento OSPF (Internet).
  • GPS e malhas viárias.
  • Games (Pathfinding, embora A* seja melhor).
Back to top