Advertisement

# FloydWarshall

Feb 26th, 2018
641
0
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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement