# Dijkstra's Algorithm

Jun 18 2019, 4:25 PM PST

## 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.