## floyd warshall

in lua

### Source Code

``````-- Floyd-Warshall "all pairs-shortest" algorithm implementation
-- See : http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

-- Note : this implementation (and tests) were roughly translated to
--  Lua from Diego Allen's implementation of the same problem.
--  See : https://github.com/kennyledet/Algorithm-Implementations/tree/master/Floyd_Warshall/Java/dalleng

-- Creates a adjacency matrix for a graph of n nodes
-- n       : the number of nodes in the graph
-- returns :  an adjacency matrix, where each (i,i) == 0 and each(i,j) == inf.
local function makeGraph(n)
local graph = {}
for i = 1, n do graph[i] = {}
for j = 1, n do
graph[i][j] = (i == j) and 0 or math.huge
end
end
return graph
end

-- Adds a weighted edge to a graph
-- g : the graph's adjacency matrix
-- s : the start node
-- e : the end node
-- w : the edge weight (can either be positive or negative)
local function addEdge(graph, s, e, w)
graph[s][e] = w
end

-- Performs Floyd-Warshall dynamic search.
-- graph   : an adjacency matrix
-- Returns : 1. a table of shortest distances
--           2. a boolean: true if negative cycles were detected, false otherwise
local function floydWarshall(graph)
local distances = {}
local n = #graph
local hasNegativeCycles = false

-- Copies the original array
for i = 1, n do distances[i] = {}
for j = 1, n do distances[i][j] = graph[i][j] end
end

-- Dynamic search
for k = 1, n do
for i = 1, n do
for j = 1, n do
distances[i][j] = math.min(distances[i][j], distances[i][k] + distances[k][j])
end
end
if distances[k][k] < 0 then hasNegativeCycles = true end
end
return distances, hasNegativeCycles
end

return {
makeGraph = makeGraph,
floydWarshall = floydWarshall
}
``````
``````-- Tests for floyd_warshall.lua
local fw = require 'floyd_warshall'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function same(t, d)
if #t ~= #d then return false end
if #t[1] ~= #d[1] then return false end
local n = #t
for i = 1,n do
for j = 1, n do
if t[i][j] ~= d[i][j] then return false end
end
end
return true
end

local H = math.huge

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing graph with positive weights', function()
local expected = {
{0, 5, 8, 9},
{H, 0, 3, 4},
{H, H, 0, 1},
{H, H, H, 0},
}
local g = fw.makeGraph(4)
local d, negCycles = fw.floydWarshall(g)
assert(same(expected, d))
assert(not negCycles)
end)

run('Testing graph with negative weights', function()
local expected = {
{0, 1, -2, 1},
{H, 0,  H, 3},
{H, H,  0, 3},
{H, H,  H, 0},
}
local g = fw.makeGraph(4)