daily pastebin goal
35%
SHARE
TWEET

FloydWarshall

Ozzypig Feb 26th, 2018 (edited) 28 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- FloydWarshall mixin for Graph class
  2. -- ModuleScript inside Graph ModuleScript
  3. -- by Ozzypig (Twitter: @Ozzypig, ozzypig.com)
  4.  
  5. -- Floyd-Warshall algorithm: shortest path between all nodes in a graph
  6. -- *    Runs in O(|V|^3) in best, worst and average cases
  7. -- *    assumes no negative cycles in a graph
  8.  
  9. local FloydWarshallMixin = {}
  10.  
  11. FloydWarshallMixin.pathsGenerated = false
  12. FloydWarshallMixin.nodeDist = nil
  13. FloydWarshallMixin.nodeNext = nil
  14.  
  15. function FloydWarshallMixin:floydWarshall()
  16.     local nodes = {}
  17.     for node in self:eachNode() do
  18.         table.insert(nodes, node)
  19.     end
  20.    
  21.     local edges = {}
  22.     for edge in self:eachEdge() do
  23.         table.insert(edges, edge)
  24.     end
  25.    
  26.     --print(("Flyod-Warshall Algorithm (Edges: %d, Vertices: %d)"):format(#edges, #nodes))
  27.    
  28.     -- |V|x|V| array of minimum distances from node i to j initialized to infinity
  29.     local nodeDist = {}
  30.     -- |V|x|V| array of vertex indices initialized to null
  31.     local nodeNext = {}
  32.     for i = 1, #nodes do
  33.         nodeDist[i] = {}
  34.         nodeNext[i] = {}
  35.         for j = 1, #nodes do
  36.             nodeDist[i][j] = math.huge
  37.             nodeNext[i][j] = nil -- redundant, but good for completeness
  38.         end
  39.     end
  40.    
  41.     -- initialize distances
  42.     for edge in self:eachEdge() do
  43.         local u, v = edge.origin.index, edge.target.index
  44.         nodeDist[u][v] = edge.value
  45.         nodeNext[u][v] = v
  46.     end
  47.    
  48.     -- the standard floyd-warshall implementation
  49.     local sum
  50.     for k = 1, #nodes do
  51.         for i = 1, #nodes do
  52.             for j = 1, #nodes do
  53.                 sum = nodeDist[i][k] + nodeDist[k][j]
  54.                 if nodeDist[i][j] > sum then
  55.                     nodeDist[i][j] = sum
  56.                     nodeNext[i][j] = nodeNext[i][k]
  57.                 end
  58.             end
  59.         end
  60.     end
  61.    
  62.     self.nodeDist = nodeDist
  63.     self.nodeNext = nodeNext
  64.     self.pathsGenerated = true
  65. end
  66.  
  67. function FloydWarshallMixin:path(nodeStart, nodeEnd)
  68.     assert(self.pathsGenerated, "Must call :floydWarshall() before :path(...) in order to generate paths")
  69.     local u, v = nodeStart.index, nodeEnd.index
  70.     local path = {}
  71.     if not self.nodeNext[u][v] then return path end
  72.     -- Recover the path
  73.     table.insert(path, self.nodesByIndex[u])
  74.     while u ~= v do
  75.         u = self.nodeNext[u][v]
  76.         table.insert(path, self.nodesByIndex[u])
  77.     end
  78.     return path
  79. end
  80.  
  81. return FloydWarshallMixin
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top