--- title: "Dijkstra em Zig: Caminho Mínimo Passo a Passo" url: "https://ziglang.com.br/algoritmos/dijkstra/" markdown_url: "https://ziglang.com.br/algoritmos/dijkstra.MD" description: "Implemente o algoritmo de Dijkstra em Zig para encontrar caminhos mínimos, reconstruir rotas e escolher entre matriz e fila de prioridade." date: "2026-08-22" author: "Zig Brasil" --- # Dijkstra em Zig: Caminho Mínimo Passo a Passo Implemente o algoritmo de Dijkstra em Zig para encontrar caminhos mínimos, reconstruir rotas e escolher entre matriz e fila de prioridade. # Dijkstra em Zig: Caminho Mínimo Passo a Passo O **algoritmo de Dijkstra** encontra o menor custo de um vértice de origem até todos os outros vértices alcançáveis de um grafo com **pesos não negativos**. Em Zig, a versão mais didática usa uma matriz de adjacência, um array de distâncias, um array de predecessores e um conjunto de vértices já finalizados. Ela executa em **O(V²)** e evita depender de APIs instáveis de fila de prioridade. A recomendação direta é: use Dijkstra quando os custos nunca forem negativos e você precisar de uma origem para vários destinos. Para um grafo esparso e grande, troque a matriz por uma lista de adjacência e uma min-heap. Se houver pesos negativos, use [Bellman-Ford em Zig](/algoritmos/bellman-ford/); se a consulta envolver todos os pares de vértices, considere [Floyd-Warshall](/algoritmos/floyd-warshall/). ## Resposta rápida | Pergunta | Resposta | |---|---| | O que Dijkstra calcula? | menor distância da origem até cada vértice | | Pesos permitidos | zero ou positivos | | Pesos negativos | não são suportados | | Versão com matriz | O(V²) de tempo e O(V²) de espaço para o grafo | | Versão com min-heap | O((V + E) log V) com lista de adjacência | | Como recuperar a rota? | seguindo o array de predecessores ao contrário | | Grafo desconectado | vértices inalcançáveis permanecem com distância infinita | | Alternativa sem pesos | BFS | | Alternativa com peso negativo | Bellman-Ford | Dijkstra aparece em mapas, roteamento de rede, planejamento de tarefas, jogos, logística e qualquer problema que possa ser modelado como “estados ligados por transições com custo”. O peso pode representar distância, tempo, consumo de energia ou preço, desde que somar arestas seja uma representação válida do custo total. ## Como o algoritmo funciona Cada vértice começa com uma distância provisória. A origem recebe zero; os demais recebem infinito. Em cada rodada, o algoritmo: 1. escolhe o vértice não visitado com a menor distância conhecida; 2. marca esse vértice como finalizado; 3. examina suas arestas de saída; 4. tenta melhorar a distância de cada vizinho; 5. registra o predecessor quando encontra uma rota melhor. A tentativa de melhorar uma distância é chamada de **relaxamento**. Para uma aresta `u → v` com peso `w`, a regra é: ```text se dist[u] + w < dist[v]: dist[v] = dist[u] + w predecessor[v] = u ``` A propriedade que faz Dijkstra funcionar é a ausência de pesos negativos. Quando `u` é o vértice aberto de menor distância, nenhuma rota futura passando por vértices mais caros consegue voltar e reduzir `dist[u]`. Portanto, sua distância pode ser considerada definitiva. ## Exemplo passo a passo Considere este grafo direcionado: ```text 0 → 1 custo 4 0 → 2 custo 1 2 → 1 custo 2 1 → 3 custo 1 2 → 3 custo 5 3 → 4 custo 3 ``` As distâncias começam assim: ```text vértice: 0 1 2 3 4 distância: 0 ∞ ∞ ∞ ∞ ``` A partir de `0`, descobrimos `1` com custo `4` e `2` com custo `1`. O próximo vértice escolhido é `2`, porque sua distância é menor. Passar por `2` melhora `1` para `3` (`1 + 2`) e encontra `3` com custo `6`. Em seguida, `1` é finalizado com custo `3`. Sua aresta até `3` melhora a distância de `6` para `4`. Finalmente, `3` leva a `4` com custo `7`. ```text vértice: 0 1 2 3 4 distância: 0 3 1 4 7 ``` O caminho até `4` é `0 → 2 → 1 → 3 → 4`. Escolher a aresta mais barata isoladamente não bastaria; Dijkstra compara o custo acumulado desde a origem. ## Implementação completa em Zig O exemplo abaixo usa `null` para representar ausência de aresta. Um peso `0` continua sendo uma aresta válida, o que evita o erro comum de confundir zero com “não conectado”. O tamanho do grafo é conhecido em tempo de compilação para manter o exemplo autocontido. ```zig const std = @import("std"); const INF = std.math.maxInt(u64); fn Resultado(comptime N: usize) type { return struct { distancias: [N]u64, predecessores: [N]?usize, }; } fn dijkstra( comptime N: usize, grafo: *const [N][N]?u64, origem: usize, ) !Resultado(N) { if (origem >= N) return error.VerticeInvalido; var distancias = [_]u64{INF} ** N; var predecessores = [_]?usize{null} ** N; var finalizados = [_]bool{false} ** N; distancias[origem] = 0; for (0..N) |_| { var atual: ?usize = null; for (0..N) |vertice| { if (finalizados[vertice]) continue; if (distancias[vertice] == INF) continue; if (atual == null or distancias[vertice] < distancias[atual.?]) { atual = vertice; } } const u = atual orelse break; finalizados[u] = true; for (grafo[u], 0..) |peso_opcional, v| { const peso = peso_opcional orelse continue; if (finalizados[v]) continue; if (distancias[u] > INF - peso) { return error.OverflowDeDistancia; } const candidata = distancias[u] + peso; if (candidata < distancias[v]) { distancias[v] = candidata; predecessores[v] = u; } } } return .{ .distancias = distancias, .predecessores = predecessores, }; } fn escreverCaminho( comptime N: usize, predecessores: *const [N]?usize, origem: usize, destino: usize, writer: anytype, ) !void { if (origem >= N or destino >= N) return error.VerticeInvalido; var invertido: [N]usize = undefined; var quantidade: usize = 0; var atual: ?usize = destino; while (atual) |vertice| { if (quantidade == N) return error.CicloNosPredecessores; invertido[quantidade] = vertice; quantidade += 1; if (vertice == origem) break; atual = predecessores[vertice]; } if (quantidade == 0 or invertido[quantidade - 1] != origem) { return error.DestinoInalcancavel; } var i = quantidade; while (i > 0) { i -= 1; try writer.print("{d}", .{invertido[i]}); if (i != 0) try writer.writeAll(" -> "); } } pub fn main() !void { const N = 5; const grafo = [N][N]?u64{ .{ null, 4, 1, null, null }, .{ null, null, null, 1, null }, .{ null, 2, null, 5, null }, .{ null, null, null, null, 3 }, .{ null, null, null, null, null }, }; const resultado = try dijkstra(N, &grafo, 0); const stdout = std.io.getStdOut().writer(); try stdout.print("Custo até 4: {d}\n", .{resultado.distancias[4]}); try stdout.writeAll("Caminho: "); try escreverCaminho(N, &resultado.predecessores, 0, 4, stdout); try stdout.writeByte('\n'); } ``` A saída esperada é: ```text Custo até 4: 7 Caminho: 0 -> 2 -> 1 -> 3 -> 4 ``` A assinatura exata de APIs de saída pode mudar entre versões do Zig antes do 1.0. A lógica do algoritmo, os arrays e o contrato de erros permanecem os mesmos; ajuste apenas a obtenção do writer se a versão do projeto usar a API de I/O mais nova. ## Entendendo as decisões do código ### Infinito e overflow `std.math.maxInt(u64)` representa uma distância ainda desconhecida. O código nunca soma um peso a `INF`, pois só escolhe vértices com distância finita. Mesmo assim, uma distância real pode estar perto do limite de `u64`; por isso, verificamos `distancias[u] > INF - peso` antes da adição. Ignorar overflow é perigoso: em um build com determinadas opções, a soma pode falhar; em outro contexto, um valor estourado poderia parecer artificialmente pequeno e corromper o resultado. ### Aresta ausente não é peso zero A matriz usa `?u64`. Assim: - `null` significa que não existe aresta; - `0` significa que existe uma aresta gratuita; - qualquer valor positivo representa seu custo. Usar zero como sentinela é comum em exemplos rápidos, mas impede grafos com arestas de custo zero e mistura dado válido com estado de controle. ### Por que guardar predecessores A distância responde “quanto custa?”, mas não “por onde passar?”. Sempre que `candidata` melhora `distancias[v]`, o código grava `u` como predecessor de `v`. A reconstrução começa no destino e caminha para trás até a origem. O array temporário `invertido` tem no máximo `N` elementos. Se a cadeia ultrapassar esse limite, há um ciclo indevido nos predecessores, sinal de bug ou corrupção de dados. ## Matriz ou fila de prioridade? A versão com matriz procura linearmente o próximo vértice em cada rodada e examina uma linha completa: ```text tempo: O(V²) espaço do grafo: O(V²) ``` Ela é uma boa escolha quando: - o grafo é pequeno; - há muitas arestas; - simplicidade importa mais que a melhor assíntota; - o tamanho é fixo ou limitado; - você quer uma implementação fácil de auditar. Para um mapa com milhões de nós e poucas conexões por nó, uma matriz desperdiça memória. Nesse caso, use uma lista de adjacência e uma **min-heap** contendo pares `(distância, vértice)`: ```text tempo: O((V + E) log V) espaço: O(V + E) ``` Ao retirar um item da heap, descarte-o se sua distância não corresponder mais ao valor atual do vértice. Essa técnica aceita entradas antigas e evita precisar de uma operação `decrease-key`, simplificando a implementação. Como as APIs de containers da biblioteca padrão podem mudar antes do Zig 1.0, encapsule a fila de prioridade atrás de uma função ou tipo do projeto. Assim, uma atualização da stdlib não espalha alterações pelo algoritmo inteiro. ## Dijkstra, BFS, Bellman-Ford ou Floyd-Warshall? | Situação | Algoritmo indicado | |---|---| | todas as arestas têm o mesmo custo | BFS | | pesos diferentes, todos não negativos | Dijkstra | | pode haver peso negativo | Bellman-Ford | | menores caminhos entre todos os pares | Floyd-Warshall | | grafo enorme e heurística disponível | A* para um destino específico | BFS é, na prática, o caso especializado em que cada aresta custa uma unidade. Ele evita a fila de prioridade. Bellman-Ford é mais flexível, mas sua complexidade O(V × E) costuma ser maior. Floyd-Warshall usa O(V³), porém produz uma matriz completa de distâncias entre todos os pares. O ponto decisivo não é qual algoritmo parece mais sofisticado, mas qual contrato os dados garantem. Se um custo negativo puder entrar por configuração, importação ou bug, valide os pesos antes de chamar Dijkstra. ## Grafos direcionados, não direcionados e desconectados O exemplo é direcionado: definir `grafo[u][v]` não cria automaticamente `grafo[v][u]`. Para uma estrada de mão dupla com o mesmo custo, preencha as duas posições. Se os custos forem diferentes por direção, mantenha valores distintos. Em um grafo desconectado, a busca termina quando não existe mais vértice aberto com distância finita. Os vértices restantes mantêm `INF` e predecessor `null`. Antes de imprimir uma distância, teste esse estado e mostre “inalcançável” em vez de exibir o maior inteiro possível. Também é válido interromper cedo quando um único destino for finalizado. Como a distância dele já é definitiva, não há motivo para explorar o restante do grafo se o produto não precisa das outras distâncias. ## Erros comuns ### Usar Dijkstra com peso negativo Este é o erro conceitual mais importante. Dijkstra pode finalizar um vértice antes de descobrir uma aresta negativa que reduziria seu custo. Não tente corrigir isso apenas permitindo `i64`; troque de algoritmo. ### Marcar como visitado cedo demais Um vértice deve ser finalizado quando é escolhido como o aberto de menor distância, não no primeiro momento em que é descoberto. Descoberta e finalização são estados diferentes. ### Somar ao infinito `INF + peso` não representa uma rota. Pule vértices inalcançáveis e faça a checagem de overflow antes de somar. ### Esquecer a direção da aresta Muitos resultados “errados” são matrizes montadas como grafo direcionado quando o problema descrevia conexões bidirecionais. Transforme cada ligação não direcionada em duas arestas. ### Recuperar só o custo Se a aplicação precisa mostrar uma rota, guarde predecessores durante o relaxamento. Tentar reconstruir depois apenas a partir das distâncias pode produzir ambiguidades e trabalho extra. ## Como testar a implementação Uma suíte útil deve cobrir: 1. origem igual ao destino, com custo zero; 2. grafo do exemplo, incluindo rota e custo; 3. vértice desconectado; 4. aresta de peso zero; 5. duas rotas com custos diferentes; 6. grafo não direcionado representado nos dois sentidos; 7. índice de origem inválido; 8. soma que excederia `u64`; 9. empate entre dois caminhos de mesmo custo; 10. grafo com um único vértice. Em empates, a distância é determinística, mas o predecessor escolhido pode depender da ordem dos vértices e das arestas. Se o produto exige uma regra específica — por exemplo, menor número de saltos ou ordem lexical — inclua esse critério no relaxamento e documente-o. Para validar a estrutura geral antes de otimizar, compare os resultados de grafos pequenos com [Floyd-Warshall em Zig](/algoritmos/floyd-warshall/). Em testes aleatórios sem pesos negativos, as distâncias calculadas a partir da mesma origem devem coincidir. ## Checklist de uso em produção - valide que nenhum peso é negativo antes de executar; - escolha um tipo numérico compatível com o maior custo acumulado; - proteja todas as somas contra overflow; - diferencie ausência de aresta de peso zero; - trate destinos inalcançáveis explicitamente; - guarde predecessores se a rota for necessária; - use lista de adjacência para grafos esparsos; - use min-heap quando O(V²) não for aceitável; - interrompa cedo se houver apenas um destino; - meça memória, tempo e tamanho real do grafo antes de sofisticar. ## Conclusão Dijkstra é a escolha padrão para **caminhos mínimos com pesos não negativos**. A implementação com matriz de adjacência é direta, auditável e suficiente para grafos pequenos ou densos. Para grafos grandes e esparsos, preserve o mesmo contrato de distâncias e predecessores, mas use lista de adjacência e fila de prioridade. A regra que evita a maior parte dos bugs é simples: confirme o domínio dos pesos antes de escolher o algoritmo. Use [Bellman-Ford](/algoritmos/bellman-ford/) quando houver valores negativos, [Floyd-Warshall](/algoritmos/floyd-warshall/) para todos os pares e [DFS em Zig](/algoritmos/dfs-busca-profundidade/) quando a tarefa for apenas percorrer ou verificar conectividade. Para praticar slices, arrays e allocators usados nessas estruturas, consulte o guia de [estruturas de dados em Zig](/estruturas-dados/).