dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Grafo:           Matriz de distâncias inicial:
  0 --3-→ 1       |  0  1  2  3
  ↑       |     --+-------------
  7       1     0 |  0  3  ∞  7
  |       ↓     1 |  ∞  0  1  ∞
  3 ←-2-- 2     2 |  ∞  ∞  0  2
  ↑       |     3 |  ∞  ∞  ∞  0
  7       ↓
  0 ←-----+     Após considerar k=0,1,2,3:
                   |  0  1  2  3
                 --+-------------
                 0 |  0  3  4  6
                 1 |  ∞  0  1  3
                 2 |  ∞  ∞  0  2
                 3 |  ∞  ∞  ∞  0

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

const INF: i64 = std.math.maxInt(i64) / 2;

/// Resultado do Floyd-Warshall.
pub const ResultadoFW = struct {
    dist: [][]i64,
    proximo: [][]i32,
    num_vertices: u32,
    allocator: Allocator,
    tem_ciclo_negativo: bool,

    pub fn deinit(self: *ResultadoFW) void {
        for (0..self.num_vertices) |i| {
            self.allocator.free(self.dist[i]);
            self.allocator.free(self.proximo[i]);
        }
        self.allocator.free(self.dist);
        self.allocator.free(self.proximo);
    }

    /// Reconstrói o caminho de u a v.
    pub fn caminho(self: *const ResultadoFW, allocator: Allocator, u: u32, v: u32) !?[]u32 {
        if (self.proximo[u][v] == -1) return null;

        var resultado = std.ArrayList(u32).init(allocator);
        var atual: u32 = u;
        while (atual != v) {
            try resultado.append(atual);
            const prox = self.proximo[atual][v];
            if (prox == -1) return null;
            atual = @intCast(@as(u32, @intCast(prox)));
        }
        try resultado.append(v);
        return resultado.toOwnedSlice();
    }
};

/// Algoritmo de Floyd-Warshall.
pub fn floydWarshall(
    allocator: Allocator,
    num_vertices: u32,
    arestas: []const struct { u: u32, v: u32, peso: i64 },
) !ResultadoFW {
    const n = num_vertices;

    // Inicializa matrizes de distância e próximo
    const dist = try allocator.alloc([]i64, n);
    const proximo = try allocator.alloc([]i32, n);

    for (0..n) |i| {
        dist[i] = try allocator.alloc(i64, n);
        proximo[i] = try allocator.alloc(i32, n);
        @memset(dist[i], INF);
        @memset(proximo[i], -1);
        dist[i][i] = 0;
    }

    // Preenche com as arestas
    for (arestas) |aresta| {
        dist[aresta.u][aresta.v] = aresta.peso;
        proximo[aresta.u][aresta.v] = @intCast(aresta.v);
    }

    // Floyd-Warshall: três loops aninhados
    for (0..n) |k| {
        for (0..n) |i| {
            for (0..n) |j| {
                if (dist[i][k] < INF and dist[k][j] < INF) {
                    const nova_dist = dist[i][k] + dist[k][j];
                    if (nova_dist < dist[i][j]) {
                        dist[i][j] = nova_dist;
                        proximo[i][j] = proximo[i][k];
                    }
                }
            }
        }
    }

    // Detecta ciclo negativo
    var tem_ciclo_negativo = false;
    for (0..n) |i| {
        if (dist[i][i] < 0) {
            tem_ciclo_negativo = true;
            break;
        }
    }

    return .{
        .dist = dist,
        .proximo = proximo,
        .num_vertices = n,
        .allocator = allocator,
        .tem_ciclo_negativo = tem_ciclo_negativo,
    };
}

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

    const ArestaFW = struct { u: u32, v: u32, peso: i64 };
    const arestas = [_]ArestaFW{
        .{ .u = 0, .v = 1, .peso = 3 },
        .{ .u = 0, .v = 3, .peso = 7 },
        .{ .u = 1, .v = 2, .peso = 1 },
        .{ .u = 2, .v = 3, .peso = 2 },
    };

    var res = try floydWarshall(allocator, 4, &arestas);
    defer res.deinit();

    try stdout.print("Matriz de distâncias:\n", .{});
    for (0..4) |i| {
        for (0..4) |j| {
            if (res.dist[i][j] >= INF) {
                try stdout.print(" INF", .{});
            } else {
                try stdout.print(" {d:>3}", .{res.dist[i][j]});
            }
        }
        try stdout.print("\n", .{});
    }

    // Caminho de 0 a 3
    if (try res.caminho(allocator, 0, 3)) |cam| {
        defer allocator.free(cam);
        try stdout.print("Caminho 0→3: ", .{});
        for (cam) |v| try stdout.print("{d} ", .{v});
        try stdout.print("(distância: {d})\n", .{res.dist[0][3]});
    }
}