52 lines
1.6 KiB
Plaintext
52 lines
1.6 KiB
Plaintext
require "table2"
|
|
require "math2"
|
|
|
|
class floydWarshall
|
|
static function do_calcs(weights, nvertices)
|
|
local dist = {}
|
|
local next = {}
|
|
for i = 1, nvertices do
|
|
dist[i] = table.rep(nvertices, 1/0)
|
|
next[i] = table.rep(nvertices, 1)
|
|
for j = 1, nvertices do
|
|
if i != j then next[i][j] = j end
|
|
end
|
|
end
|
|
for weights as w do dist[w[1]][w[2]] = w[3] end
|
|
for k = 1, nvertices do
|
|
for i = 1, nvertices do
|
|
for j = 1, nvertices do
|
|
if (dist[i][k] + dist[k][j] < dist[i][j]) then
|
|
dist[i][j] = dist[i][k] + dist[k][j]
|
|
next[i][j] = next[i][k]
|
|
end
|
|
end
|
|
end
|
|
end
|
|
floydWarshall.print_result(dist, next)
|
|
end
|
|
|
|
static function print_result(dist, next)
|
|
print("pair dist path")
|
|
for i = 1, #next do
|
|
for j = 1, #next do
|
|
if i != j then
|
|
local u = i
|
|
local v = j
|
|
local path = string.format("%d -> %d %2d %s", u, v, math.trunc(dist[i][j]), u)
|
|
while true do
|
|
u = next[u][v]
|
|
path ..= " -> " .. u
|
|
if u == v then break end
|
|
end
|
|
print(path)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
local weights = { {1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1} }
|
|
local nvertices = 4
|
|
floydWarshall.do_calcs(weights, nvertices)
|