Algoritmo de Dijkstra com fila de prioridades

O algoritmo de Dijkstra encontra o caminho mais curto de um único nó de origem até todos os outros nós em um grafo ponderado com pesos de arestas não negativos. Ele funciona processando os nós de forma gulosa, na ordem de sua melhor distância conhecida — sempre expandindo o nó não visitado mais próximo. A estrutura de dados fundamental é um heap mínimo (fila de prioridade), que recupera com eficiência o nó com a menor distância.

Algoritmo de Dijkstra: (1) Inicialize dist[source] = 0 e dist[all others] = inf. (2) Insira (0, source) em um heap mínimo. (3) Remova o nó u com a menor distância. Se ele já tiver sido visitado com uma distância menor, ignore-o. (4) Para cada vizinho v de u: se dist[u] + weight(u,v) < dist[v], atualize dist[v] e insira (dist[v], v) no heap. (5) Repita até o heap ficar vazio.

O heapq do Python implementa um heap mínimo. Representamos o grafo como uma lista de adjacência: graph[u] = [(v, weight), ...]. O heap armazena tuplas (distance, node). Usamos um conjunto visited para ignorar entradas obsoletas do heap — entradas inseridas antes de uma rota melhor ser encontrada.

Considere um grafo com 5 nós e arestas: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Os caminhos mais curtos a partir do nó 0 são: até 1, passando por 0→2→1, com custo 3; até 2, com custo 1; até 3, passando por 0→2→1→3, com custo 4; até 4, passando por 0→2→1→3→4, com custo 7. Dijkstra encontra todos esses caminhos em uma única passagem, não apenas o caminho até um único alvo.

A correção de Dijkstra depende do fato de que, assim que um nó é removido do heap mínimo, sua distância é definitiva. Isso só é válido quando os pesos das arestas não são negativos. Com uma aresta negativa u→v de peso -5, depois de visitar v, podemos encontrar um caminho passando por u que seja mais curto — mas v já está marcado como visitado. Uma única aresta negativa pode invalidar todos os cálculos de distância subsequentes.

Este problema acrescenta uma restrição: no máximo k escalas. O Dijkstra padrão não trata a contagem de etapas nativamente. Solução: amplie o estado para (cost, node, stops_remaining). Use Dijkstra com essa 3-tupla ou use Bellman-Ford com k+1 passagens de relaxamento. O Dijkstra modificado para quando stops_remaining chega a 0, impedindo novos saltos.

Com um heap binário, Dijkstra é executado em O((V + E) log V) de tempo: cada vértice é removido uma vez (V remoções), cada aresta pode provocar uma inserção (E inserções) e cada operação no heap custa O(log V). Com um heap de Fibonacci, o limite melhora para O(E + V log V), mas o heapq do Python é um heap binário. Para grafos esparsos (E ≈ V), a versão com heap binário é O(V log V); para grafos densos (E ≈ V²), ela é O(V² log V).

Para recuperar o caminho real (não apenas as distâncias), mantenha um vetor prev: ao atualizar dist[v], defina prev[v] = u. Depois que o algoritmo terminar, reconstrua o caminho da origem ao destino percorrendo-o de trás para frente: comece em dst, siga os ponteiros de prev até source e inverta o resultado.

Quando os nós são strings ou inteiros não consecutivos, use um defaultdict(list) para a lista de adjacência e um dict comum para as distâncias. Isso é comum em problemas do LeetCode, como o de tempo de atraso da rede, em que os nós são identificados pelos números de 1 a n. Lembre-se de usar dist = {node: inf for node in all_nodes} e verificar os nós inalcançáveis depois do algoritmo.

Para grafos não ponderados, BFS encontra os caminhos mais curtos em O(V + E) — mais rapidamente que o Dijkstra, com O((V+E) log V). Dijkstra generaliza BFS para grafos ponderados usando uma fila de prioridade em vez de uma fila comum FIFO. Quando todos os pesos das arestas são iguais, Dijkstra se reduz a BFS. Escolha BFS para grafos não ponderados, Dijkstra para pesos não negativos e Bellman-Ford para pesos negativos.

O Dijkstra dos livros didáticos usa uma fila de prioridade com redução da chave: quando a distância de um nó melhora, atualiza sua prioridade no próprio local. Isso exige um heap de Fibonacci para obter O(E + V log V), mas é difícil de implementar. A abordagem de remoção preguiçosa usada em entrevistas insere uma nova entrada e ignora as remoções obsoletas — é mais simples, com apenas um custo adicional constante. Em Python, a remoção preguiçosa com heapq é a implementação padrão em entrevistas.

Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Nesta lição, você aprendeu que: Dijkstra usa um heap mínimo para processar avidamente os nós na ordem da melhor distância atual, é executado em O((V+E) log V) de tempo e falha com arestas de peso negativo e as entradas obsoletas do heap são tratadas verificando um conjunto de visitados ao removê-las. Em seguida, veremos Bellman-Ford, que trata pesos negativos por meio de n-1 passagens de relaxamento.