Dijsktra's Algorithm in Lua

dijkstra.lua

-- Dijkstra's Algorithm
-- g: a graph of all nodes
-- source: id of start node
function getAllPaths(g, source)

	dist = {}
	prev = {}

	q = {}  -- "queue"
	-- init values
	for k,v in pairs(g) do
		dist[k] = INF -- "infinity"
		q[k] = g[k]
	end
	-- distance from source to source
	dist[source] = 0

	-- return key of node with min distance
	min = function (t)
		local min_key = next(t)
		local min_val = dist[min_key]
		for k,v in pairs(t) do
			if dist[k] < min_val then
				min_key, min_val = k, dist[k]
			end
		end
		return min_key
	end

	-- loop nodes
	u = min(q)
	while u do
		-- for each neighbor v of u
		for _,v in pairs(q[u].edges) do
			alt = dist[u] + 1
			if alt < dist[v] then
				dist[v] = alt
				prev[v] = u
			end
		end

		-- remove node from q
		q[u] = nil

		-- get next node
		u = min(q)
	end

	paths = {}
	-- generate paths
	for k,distance in pairs(dist) do
		path = {}
		previous = prev[k]
		while previous do
			table.insert(path, previous)
			previous = prev[previous]
		end
		-- save path to root
		paths[k] = path
	end

	return paths
end