# Dijkstra's Algorithm

# Dijkstra's Algorithm

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

- It adds a starting node to the
`closed`

set. - 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. - It finds the node with the shortest distance.
- It adds the node to
`closed`

set. If node is the goal, the process ends. Otherwise, it repeats from step 2.