Hoje O Dia Vai Ser Mais Curto

Entendendo algoritmos de caminho mais curto na prática

A maioria dos programadores encontra isso pela primeira vez em disciplinas de estruturas de dados e imediatamente acha que é só aplicar o algoritmo do Dijkstra e pronto. Na vida real, rima é assim tão simples. Você constrói o grafo, roda a função, e torce para que o resultado faça sentido. O problema é que grafos do mundo real nunca obedecem às premissas teóricas.

O algoritmo de Dijkstra resolve o caminho mais curto de um vértice fonte para todos os outros em grafos com pesos não negativos. Funciona assim: você mantém uma fila de prioridade com os nós a explorar, começa pelo vértice origem com distância zero, e a cada iteração relaxa os vizinhos. Se encontrar um caminho melhor, atualiza a distância e reposiciona na fila. A complexidade é O((V + E) log V) com heap binário. Parece direto até você tentar rodar isso em um grafo com milhares de vértices e arestas dinâmicas.

hoje o dia vai ser mais curto se você souber o que está fazendo

Aqui vai um exemplo concreto do tipo de dor que ninguém avisa. Trabalhava num sistema de roteirização para entregas urbanas onde o grafo tinha cerca de 40 mil interseções e 120 mil arestas. O Dijkstra puro levava em média 3,2 segundos por query. O SLA do negócio era 500ms. Precisávamos de algo drasticamente mais rápido sem sacrificar precisão. A solução que funcionou foi combinar Dijkstra com técnica de contração de hierarquias (Node Contraction Hierarchies). Basicamente, você pré-processa o grafo adicionando arestas de atalho para nós considerados menos importantes, criando uma hierarquia artificial. No runtime, o algoritmo só explora os níveis hierárquicos relevantes. O resultado foi queda de 3,2 segundos para 18ms por query. O preço foi um pré-processamento de cerca de 12 minutos e aumento de memória em aproximadamente 40%

.

Agora, tem um detalhe que muita gente erra. O Dijkstra não funciona com pesos negativos. Se seu grafo tiver arestas com peso negativo, mesmo que não haja ciclos negativos, o algoritmo vai falhar silenciosamente e retornar caminhos errados. A tentação é simplesmente transformar todos os pesos em positivos somando uma constante, mas isso quebra o conceito de minimalidade. A resposta certa é o algoritmo de Bellman-Ford ou, se quiser performance, o SPFA (Shortest Path Faster Algorithm), que é uma do Bellman-Ford com fila. O SPFA é rápido na prática mas tem pior caso exponencial, então dependa dele com cautela.

Implementação funcional em Python

Vou mostrar uma implementação limpa do Dijkstra usando heapq do Python. Não é otimizada para produção massiva, mas serve para entender a lógica central e rodar em grafos moderados.

```python import heapq def dijkstra(graph, source): distances = {node: float('inf') for node in graph} distances[source] = 0 pq = [(0, source)] visited = set() while pq: current_dist, current_node = heapq.heappop(pq) if current_node in visited: continue visited.add(current_node) for neighbor, weight in graph[current_node].items(): distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(pq, (distance, neighbor)) return distances Exemplo de uso: graph = { 'A': {'B': 4, 'C': 2}, 'B': {'C': 1, 'D': 5}, 'C': {'B': 3, 'D': 8}, 'D': {} } result = dijkstra(graph, 'A') print(result) {'A': 0, 'B': 3, 'C': 2, 'D': 8} ```

O grafo é representado como um dicionário aninhado onde cada chave é um nó e o valor é outro dicionário com os vizinhos e seus pesos. A fila de prioridade usa tuplas (distância, nó), o que funciona perfeitamente porque o heapq do Python compara tuplas elemento por elemento. A verificação `if current_node in visited` evita processar nós já resolvidos, o que é importante porque podemos empurrar o mesmo nó na fila múltiplas vezes com distâncias diferentes.

Armadilhas comuns e como evitá-las

O primeiro erro típico é esquecer que o Dijkstra assume que, uma vez que um nó é marcado como visitado, sua distância final já está determinada. Isso só é verdade com pesos não negativos. Já vi gente aplicar Dijkstra em grafos de custo temporal onde "peso negativo" aparecia na forma de ganho de tempo em certas rotas. O algoritmo simplesmente devolvia resultados incorretos e o debug demorou horas porque o erro era conceitual, não de implementação. Outro problema frequente é a representação do grafo. Usar listas de adjacência é quase sempre melhor que matriz de adjacência para grafos esparsos. Matriz de adjacência consome O(V²) de memória e o Dijkstra com ela fica O(V²), o que é aceitável apenas para grafos pequenos e densos. Para grafos esparsos como os que encontro no dia a dia, lista de adjacência com heap dá O((V + E) log V), que escala infinitamente melhor.

Se você precisa de caminhos mais curtos entre todos os pares de vértices, não rode o Dijkstra V vezes. O algoritmo de Floyd-Warshall resolve isso em O(V³) com código absurdamente mais simples e, para grafos com até talvez 500 vértices, frequentemente sai mais rápido na prática por causa das constantes menores e da boa localidade de cache. Para grafos maiores, use Johnson's algorithm, que combina Dijkstra com Bellman-Ford de forma elegante e roda em O(V² log V + VE).

Quando NÃO usar Dijkstra

Há cenários onde Dijkstra é simplesmente a ferramenta errada. Se o grafo é muito grande e dinâmico — adicionando e removendo arestas constantemente — o custo de recalculção completa pode inviabilizar o uso. Nesse caso, considere algoritmos de rota dinâmicos como D* Lite, usado em robótica e navegação onde o mapa muda enquanto o agente se move. Também existem técnicas de landmark-based distance estimation (como o ALT algorithm) que usam heurísticas admissíveis derivadas de landmarks para acelerar buscas A* sem sacrificar optimalidade. Outro caso é quando você não precisa do caminho exato mais curto, mas de uma resposta rápida com margem de erro aceitável. Algoritmos de contração de hierarquias que mencionei antes entram aqui, junto com técnicas de sampling e aproximação. Em sistemas de navegação como Google Maps e Waze, nenhum deles roda Dijkstra puro em tempo real. Eles usam combinações de preprocessing pesado, hierarquias, e heurísticas customizadas que cortam drasticamente o espaço de busca.

Obrigatório mencionar também o caso de grafos com restrições adicionais. Se você precisa do caminho mais curto sujeito a constraints como "no máximo 3 turns" ou "passar necessariamente por este nodo intermediário", o Dijkstra padrão não resolve. Você precisa estender o estado do grafo para incluir essas restrições como dimensões adicionais, o que aumenta exponencialmente o espaço de estados. Nesses casos, frequentemente vale mais a pena usar programação dinâmica ou buscas com poda ao invés de tentar adaptar o Dijkstra. No fim das contas, o algoritmo de caminho mais curto certo depende inteiramente do seu grafo: tamanho, densidade, presença de pesos negativos, dinâmica, e constraints adicionais. Não existe solução única. Teste, meça, e escolha com base nos dados do seu problema específico, não em recomendações genéricas da internet.