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