Grafo direcionado com peso negativo:
    0 --6--> 1 --5--> 2
    |        ↑       /
    7       -2     -4
    |        |    /
    v        3 <--
    4 --(-3)-> 3

Bellman-Ford a partir de 0:

Iteração 0: dist = [0, ∞, ∞, ∞, ∞]
Iteração 1: dist = [0, 6, 11, ∞, 7]    (relaxa 0→1, 0→4, 1→2)
Iteração 2: dist = [0, 6, 11, 4, 7]     (relaxa 4→3)
Iteração 3: dist = [0, 2, 7, 4, 7]      (relaxa 3→1, 1→2)
Iteração 4: dist = [0, 2, 7, 4, 7]      (sem mudanças)

Verificação extra: sem ciclo negativo ✓

const std = @import("std");
const Allocator = std.mem.Allocator;

const Aresta = struct {
    origem: u32,
    destino: u32,
    peso: i64,
};

/// Resultado do Bellman-Ford.
const ResultadoBF = struct {
    dist: []i64,
    pai: []i32,
    tem_ciclo_negativo: bool,
};

/// Algoritmo de Bellman-Ford.
pub fn bellmanFord(
    allocator: Allocator,
    num_vertices: u32,
    arestas: []const Aresta,
    origem: u32,
) !ResultadoBF {
    const INF: i64 = std.math.maxInt(i64) / 2;

    const dist = try allocator.alloc(i64, num_vertices);
    @memset(dist, INF);

    const pai = try allocator.alloc(i32, num_vertices);
    @memset(pai, -1);

    dist[origem] = 0;

    // V-1 iterações de relaxamento
    var i: u32 = 0;
    while (i < num_vertices - 1) : (i += 1) {
        var houve_mudanca = false;

        for (arestas) |aresta| {
            if (dist[aresta.origem] < INF) {
                const nova_dist = dist[aresta.origem] + aresta.peso;
                if (nova_dist < dist[aresta.destino]) {
                    dist[aresta.destino] = nova_dist;
                    pai[aresta.destino] = @intCast(aresta.origem);
                    houve_mudanca = true;
                }
            }
        }

        // Otimização: se nada mudou, pode parar
        if (!houve_mudanca) break;
    }

    // Verificação de ciclo negativo (V-ésima iteração)
    var tem_ciclo_negativo = false;
    for (arestas) |aresta| {
        if (dist[aresta.origem] < INF) {
            if (dist[aresta.origem] + aresta.peso < dist[aresta.destino]) {
                tem_ciclo_negativo = true;
                break;
            }
        }
    }

    return .{
        .dist = dist,
        .pai = pai,
        .tem_ciclo_negativo = tem_ciclo_negativo,
    };
}

/// Reconstrói o caminho da origem ao destino.
pub fn reconstruirCaminho(allocator: Allocator, pai: []const i32, destino: u32) ![]u32 {
    var caminho = std.ArrayList(u32).init(allocator);
    var atual: i32 = @intCast(destino);
    while (atual != -1) {
        try caminho.insert(0, @intCast(@as(u32, @intCast(atual))));
        atual = pai[@intCast(@as(u32, @intCast(atual)))];
    }
    return caminho.toOwnedSlice();
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const arestas = [_]Aresta{
        .{ .origem = 0, .destino = 1, .peso = 6 },
        .{ .origem = 0, .destino = 4, .peso = 7 },
        .{ .origem = 1, .destino = 2, .peso = 5 },
        .{ .origem = 2, .destino = 3, .peso = -4 },
        .{ .origem = 3, .destino = 1, .peso = -2 },
        .{ .origem = 4, .destino = 3, .peso = -3 },
    };

    const res = try bellmanFord(allocator, 5, &arestas, 0);
    defer allocator.free(res.dist);
    defer allocator.free(res.pai);

    if (res.tem_ciclo_negativo) {
        try stdout.print("Ciclo negativo detectado!\n", .{});
    } else {
        try stdout.print("Distâncias de 0:\n", .{});
        for (res.dist, 0..) |d, i| {
            if (d < std.math.maxInt(i64) / 2) {
                try stdout.print("  0 → {d}: {d}\n", .{ i, d });
            } else {
                try stdout.print("  0 → {d}: inalcançável\n", .{i});
            }
        }

        const caminho = try reconstruirCaminho(allocator, res.pai, 3);
        defer allocator.free(caminho);
        try stdout.print("Caminho 0→3: ", .{});
        for (caminho) |v| try stdout.print("{d} ", .{v});
        try stdout.print("\n", .{});
    }
}