Algoritmo de Dijkstra

O algoritmo de Dijkstra, desenvolvido por Edsger Dijkstra em 1956, encontra o caminho mais curto de um vértice origem até todos os outros vértices em um grafo ponderado com pesos de aresta não negativos. Ele é a base da navegação GPS, do roteamento de redes (protocolo OSPF), e de serviços de mapas como o Google Maps.

Ideia-chave: expansão gulosa

O algoritmo de Dijkstra é um exemplo de livro-texto de algoritmo guloso aplicado ao problema do caminho mais curto da teoria dos grafos: ele mantém um conjunto de vértices cuja distância mais curta a partir da origem já é conhecida (o conjunto resolvido) e uma fila de prioridade de candidatos ordenados por sua melhor estimativa de distância atual. A cada passo, ele extrai o vértice não resolvido mais próximo, finaliza sua distância, e relaxa suas arestas de saída.

A correção depende de pesos não negativos: uma vez que um vértice é resolvido, nenhum caminho futuro através de outros vértices pode melhorar sua distância. Com pesos negativos, essa garantia falha, e o Bellman-Ford deve ser usado em vez disso.

O algoritmo

Entrada: um grafo direcionado ponderado \(G = (V, E, w)\) com \(w(u,v) \geq 0\), e um vértice origem \(s\).

Saída: \(d[v]\) = distância mais curta de \(s\) a \(v\), e \(\text{prev}[v]\) = predecessor de \(v\) no caminho mais curto.

Inicialização:

\[d[s] = 0, \quad d[v] = \infty \;\forall v \neq s, \quad \text{prev}[v] = \text{Nenhum} \;\forall v\]

Insira todos os vértices em uma fila de prioridade mínima \(Q\) com chave \(d[v]\).

Loop principal: enquanto \(Q\) não estiver vazia:

  1. Extraia \(u = \arg\min_{v \in Q} d[v]\) (vértice com a menor distância tentativa).
  2. Para cada vizinho \(v\) de \(u\) com peso de aresta \(w(u,v)\):
    • Relaxamento: se \(d[u] + w(u,v) < d[v]\), atualize \(d[v] \leftarrow d[u] + w(u,v)\) e \(\text{prev}[v] \leftarrow u\).
  3. Remova \(u\) de \(Q\).

O passo de relaxamento é o coração do algoritmo: ele pergunta “o caminho através de \(u\) é mais curto do que o melhor caminho conhecido até \(v\)?”

Exemplo passo a passo

Encontre os caminhos mais curtos a partir de A neste grafo:

Grafo direcionado ponderado usado no exemplo passo a passo de Dijkstra com cinco nós

Tabela de iterações (origem = A):

Passo Resolvido \(d[A]\) \(d[B]\) \(d[C]\) \(d[D]\) \(d[E]\)
Início - 0 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
1 A 0 4 2 \(\infty\) \(\infty\)
2 C 0 4 2 5 10
3 B 0 4 2 5 10
4 D 0 4 2 5 7
5 E 0 4 2 5 7

Caminhos mais curtos a partir de A:

  • A \(\to\) B: custo 4 (direto)
  • A \(\to\) C: custo 2 (direto)
  • A \(\to\) D: custo 5 (A-C-D)
  • A \(\to\) E: custo 7 (A-C-D-E)

Mesmo grafo com a árvore de caminhos mais curtos destacada mostrando as rotas ótimas de A para todos os outros nós

Complexidade

A complexidade depende da implementação da fila de prioridade:

Implementação Extract-min Decrease-key Complexidade total
Array (ingênua) \(O(V)\) \(O(1)\) \(O(V^2)\)
Heap binária \(O(\log V)\) \(O(\log V)\) \(O((V+E)\log V)\)
Heap de Fibonacci \(O(\log V)\) \(O(1)\) amortizado \(O(E + V\log V)\)

Para grafos densos (\(E \approx V^2\)): a implementação com array é ótima em \(O(V^2)\). Para grafos esparsos (\(E = O(V)\) ou \(O(V\log V)\)): a heap binária dá \(O(V\log V)\), muito melhor. A heap de Fibonacci é teoricamente ótima, mas raramente usada na prática devido às grandes constantes.

A maioria das redes reais (redes rodoviárias, tabelas de roteamento da internet) são esparsas, então a versão com fila de prioridade é o padrão.

Reconstruindo o caminho mais curto

O array \(\text{prev}[]\) registra o predecessor de cada vértice no caminho mais curto. Para recuperar o caminho de \(s\) até um alvo \(t\):

path <- c()
current <- t
while (!is.null(current)) {
  path <- c(current, path)
  current <- prev[current]
}
# path is now: s -> ... -> t

Isso retrocede de \(t\) a \(s\) em tempo \(O(V)\).

Quando Dijkstra falha: pesos negativos

A suposição gulosa por trás de Dijkstra, de que uma vez que um vértice é resolvido sua distância nunca pode melhorar, quebra assim que uma aresta negativa entra no grafo.

⚠️ O algoritmo de Dijkstra é incorreto para grafos com pesos de aresta negativos

Com pesos negativos, resolver um vértice não garante que sua distância mais curta foi encontrada: um caminho posterior através de uma aresta negativa poderia ser mais curto. Exemplo:

  • A \(\to\) B: peso 3
  • A \(\to\) C: peso 5
  • C \(\to\) B: peso \(-4\)

Dijkstra resolve B com distância 3. Mas o caminho A-C-B tem distância \(5 + (-4) = 1 < 3\). Dijkstra nunca reconsidera B depois de resolvê-lo, então retorna a resposta errada.

Para grafos com pesos negativos (mas sem ciclos negativos), use Bellman-Ford: complexidade \(O(VE)\), mas lida com pesos negativos corretamente. Para ciclos negativos (nenhum caminho mais curto existe), Bellman-Ford os detecta.

Grafo pequeno mostrando onde Dijkstra falha com uma aresta de peso negativo

Variantes e extensões

Variante Problema Algoritmo
Pesos negativos Caminhos mais curtos Bellman-Ford \(O(VE)\)
Caminhos mais curtos entre todos os pares Todo par \((u,v)\) Floyd-Warshall \(O(V^3)\)
Grafo não ponderado Caminho mais curto por saltos BFS \(O(V+E)\)
Heurística disponível Alvo único A* (mais rápido na prática)
Grafo dinâmico Arestas mudam ao longo do tempo D* ou LPA*

O algoritmo A* estende Dijkstra com uma função heurística \(h(v)\) que estima a distância de \(v\) até o alvo, concentrando a busca e reduzindo o número de vértices explorados. É o padrão em pathfinding de jogos e robótica.

💡 Dijkstra em R

library(igraph)

# Build the graph
g <- graph_from_data_frame(
  data.frame(from=c("A","A","B","B","C","C","D"),
             to  =c("B","C","C","D","D","E","E"),
             weight=c(4,2,1,5,3,8,2)),
  directed=TRUE
)

# Shortest distances from A
distances(g, v="A", weights=E(g)$weight)

# Shortest path from A to E (with vertex sequence)
shortest_paths(g, from="A", to="E", weights=E(g)$weight)$vpath

# All-pairs shortest paths
distances(g, weights=E(g)$weight)