Problem

Dijkstra’s Algorithm is a shortest path tree pathfinding algorithm. It compares the distance that has been traveled from the start node to the current node to find the shortest path.

Solution

local function Dijkstra(start, finish, nodes)
– Create a closed and open set
local open = {}
local closed = {}

-- Attach data to all nodes without modifying them
local data = {}
for _, node in pairs(nodes) do
	data[node] = {
		distance = math.huge,
		previous = nil
	}
end

-- The start node has a distance of 0 and starts in the open set
open[start] = true
data[start].distance = 0

while true do
	-- Pick the nearest open node
	local best = nil
	for node in pairs(open) do
		if not best or data[o].distance < data[best].distance then
			best = o
		end
	end

	--at the finish - stop looking
	if best == finish then break end

	--all nodes traversed - finish not found! No connection between start and finish
	if not best then return end

	--calculate a new score for each neighbour
	for _, neighbor in ipairs(best:neighbors()) do
		--provided it's not already in the closed set
		if not closed[neighbor] then
			local newdist = data[best].distance + best:distanceTo(neighbor)
			if newdist < data[neighbor].distance then
				data[neighbor].distance = newdist
				data[neighbor].previous = best
				open[neighbor] = true -- add newly discovered node to set of open nodes
			end
		end
	end

	--move the node to the closed set
	closed[best] = true
	open[best] = nil
end

--walk backwards to reconstruct the path
local path = {}
local at = finish
while at ~= start do
	table.insert(path, 0, at)
	at = data[at].previous
end

return path

end

Discussion

Based on the function above, Dijkstra’s Algorithm works as follows:

1. It adds a starting node to the closed set.
2. For every node in the closed set, it finds all the adjacent nodes and adds the distance traveled from the parent node to the distance to the next node. If there are two nodes in the closed set that share a neighbor, it gives the neighboring node the shorter distance.
3. It finds the node with the shortest distance.
4. It adds the node to closed set. If node is the goal, the process ends. Otherwise, it repeats from step 2.