floyd warshall


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

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,
  addEdge = addEdge,
  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)
  fw.addEdge(g, 1, 2,  5)
  fw.addEdge(g, 1, 3,  9)
  fw.addEdge(g, 1, 4, 10)
  fw.addEdge(g, 2, 3,  3)
  fw.addEdge(g, 3, 4,  1)
  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)
  fw.addEdge(g, 1, 2,  1)
  fw.addEdge(g, 1, 3, -2)
  fw.addEdge(g, 2, 4,  3)
  fw.addEdge(g, 3, 5,  3)
  local d, negCycles = fw.floydWarshall(g)
  assert(same(expected, d))
  assert(negCycles)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))