require "table2"
require "math2"

class floydWarshall
    static function do_calcs(weights, nvertices)
        local dist = {}
        local next = {}
        for i = 1, nvertices do
            dist[i] = table.rep(nvertices, 1/0)
            next[i] = table.rep(nvertices, 1)
            for j = 1, nvertices do
                if i != j then next[i][j] = j end
            end
        end
        for weights as w do dist[w[1]][w[2]] = w[3] end
        for k = 1, nvertices do
            for i = 1, nvertices do
                for j = 1, nvertices do
                    if (dist[i][k] + dist[k][j] < dist[i][j]) then
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next[i][j] = next[i][k]
                    end
                end
            end
        end
        floydWarshall.print_result(dist, next)
    end

    static function print_result(dist, next)
        print("pair     dist    path")
        for i = 1, #next do
            for j = 1, #next do
                if i != j then
                    local u = i
                    local v = j
                    local path = string.format("%d -> %d    %2d     %s", u, v, math.trunc(dist[i][j]), u)
                    while true do
                        u = next[u][v]
                        path ..=  " -> " .. u
                        if u == v then break end
                    end
                    print(path)
                end
            end
        end
    end
end

local weights = { {1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1} }
local nvertices = 4
floydWarshall.do_calcs(weights, nvertices)