Skip to content

Instantly share code, notes, and snippets.

@uraraurara
Created October 4, 2012 02:43
Show Gist options
  • Save uraraurara/3831169 to your computer and use it in GitHub Desktop.
Save uraraurara/3831169 to your computer and use it in GitHub Desktop.
dijkstra in lua
require('dumper')
function dump(...)
print( DataDumper(...), "\n---")
end
path = { {},{},{},{},{},{}}
dpath = {}
dpath[1] = { {2, 5}, { 6, 4}, {5,2} }
dpath[2] = { {3, 6}, {6, 2}, }
dpath[3] = { {4, 4} }
dpath[4] = { {6,2 }, {5, 6}}
dpath[5] = { {6,3} }
dpath[6] = {}
path_size = 6
-- Setting a Start and Goal Flag
START = 1
GOAL = 3
for i,v in ipairs(dpath)
do
for j, val in ipairs(v)
do
idx, cost = val[1], val[2]
table.insert( path[idx], {i,cost} )
end
end
for i,v in ipairs(path) do
for j, v2 in ipairs(v) do
table.insert(dpath[i], v2)
end
end
-- http://www.deqnotes.net/acmicpc/dijkstra/
fixed = {}
updated = {}
undefined = 10000000
for i = 1, path_size do
fixed[i] = false
updated[i] = undefined
end
fixed[START] = false
updated[START] = 0
update = false
while (true) do
min = 10000
fidx, ncost = -1, 10000
for afix, acost in ipairs(updated) do
if fixed[afix] == false and acost ~= undefined and ncost > acost then
ncost = acost
fidx = afix
update = true
end
end
if not update then break end
fixed[fidx] = true
if fidx == GOAL then
print("GOAL: cost", updated[GOAL] )
break
end
acost = updated[fidx]
update = false
for from, v in ipairs(dpath) do
if from == fidx then
for no, v2 in ipairs(v) do
to, tocost = v2[1], v2[2]
if updated[to] > acost + tocost then
updated[to] = acost + tocost
update = true
end
end
end
end
if not update then
break
end
end
@uraraurara
Copy link
Author

How to write more simply in lua?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment