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; se a consulta envolver todos os pares de vértices, considere Floyd-Warshall.

Resposta rápida

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 é:

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:

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:

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.

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.

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 é:

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:

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):

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?

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. 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 quando houver valores negativos, Floyd-Warshall para todos os pares e DFS em Zig 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.