shortestpath.lua

-- Define infinity.
local INF = math.huge

-- The Floyd–Warshall algorithm.
local function floydWarshall(dist)
        local n = #dist
        -- For each intermediate node k.
        for k = 1, n do
                local dk = dist[k] -- local reference to row k (for performance)
                for i = 1, n do
                        local dik = dist[i][k]
                        -- Only consider if there is a path from i to k.
                        if dik < INF then
                                local di = dist[i]
                                for j = 1, n do
                                        local candidate = dik + dk[j]
                                        if candidate < di[j] then
                                                di[j] = candidate
                                        end
                                end
                        end
                end
        end
end

-- Test the algorithm on a 500-node graph.
local function testFloydWarshall()
        local n = 500
        local graph = {}

        -- Seed the random number generator.
        math.randomseed(os.time())

        -- Create the graph.
        for i = 1, n do
                graph[i] = {}
                for j = 1, n do
                        if i == j then
                                graph[i][j] = 0
                        else
                                -- With 20% probability there is an edge with a random weight 1 to 10;
                                -- otherwise, there is no direct edge (INF).
                                if math.random() < 0.20 then
                                        graph[i][j] = math.random(1, 500)
                                else
                                        graph[i][j] = INF
                                end
                        end
                end
        end

        print("Graph with " .. n .. " nodes created. Running Floyd–Warshall...")

        local start_time = os.clock()
        floydWarshall(graph)
        local elapsed_time = os.clock() - start_time

        print("Floyd–Warshall completed in " .. elapsed_time .. " seconds.")

        -- Show sample distances.
        local samplePairs = { { 1, n }, { math.floor(n / 2), math.floor(n * 0.8) } }
        for _, pair in ipairs(samplePairs) do
                local i, j = pair[1], pair[2]
                local d = graph[i][j]
                if d == INF then
                        print("No path from node " .. i .. " to node " .. j)
                else
                        print("Shortest distance from node " .. i .. " to node " .. j .. " is " .. d)
                end
        end
end

-- Test the Floyd–Warshall algorithm on a 500-node chain graph.
local function testFloydWarshall500()
        local n = 500
        local graph = {}

        -- Initialize the graph:
        --   - The diagonal is 0 (distance from a node to itself).
        --   - All other entries are set to INF (no direct connection yet).
        for i = 1, n do
                graph[i] = {}
                for j = 1, n do
                        if i == j then
                                graph[i][j] = 0
                        else
                                graph[i][j] = INF
                        end
                end
        end

        -- Build a chain:
        -- For nodes 1 through n-1, connect node i to node i+1 and vice versa with weight 1.
        for i = 1, n - 1 do
                graph[i][i + 1] = 1
                graph[i + 1][i] = 1
        end

        print("Starting Floyd–Warshall on a 500-node chain graph...")
        local start_time = os.clock()
        floydWarshall(graph)
        local elapsed_time = os.clock() - start_time
        print(string.format("Floyd–Warshall completed in %.4f seconds.", elapsed_time))

        -- Verify the results.
        -- For a chain graph, the expected distance between nodes i and j is |i - j|.
        local testPassed = true
        for i = 1, n do
                for j = 1, n do
                        local expected = math.abs(i - j)
                        if graph[i][j] ~= expected then
                                print(
                                        string.format(
                                                "Test failed at node pair (%d, %d): expected %d, got %s",
                                                i,
                                                j,
                                                expected,
                                                tostring(graph[i][j])
                                        )
                                )
                                testPassed = false
                                break
                        end
                end
                if not testPassed then
                        break
                end
        end

        if testPassed then
                print("Test passed: All distances match the expected chain distances.")
        end
end
-- verify correctness on chain graph
testFloydWarshall500()
-- Test again on random graph
testFloydWarshall()