## dijkstra search

### Data

in lua

#### Tags

graphs, routing, search

### Source Code

``````-- Generic Dijkstra graph search algorithm implementation
-- See : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

-- Notes : this is a generic implementation of Dijkstra graph search algorithm.
-- It is devised to be used on any type of graph (point-graph, tile-graph,
-- or whatever. It expects to be initialized with a handler, which acts as
-- an interface between the search algorithm and the search space.

-- This implementation uses internally a binary heap to handle fast retrieval
-- of the lowest-cost node.

-- The Dijkstra class expects a handler to be initialized. Roughly said, the handler
-- is an interface between your search space and the generic search algorithm.
-- This model ensures flexibility, so that this generic implementation can be
-- adapted to search on any kind of space.
-- The passed-in handler should implement those functions.
-- handler.getNode(...)    -> returns a Node (instance of node.lua)
-- handler.getAllNodes()   -> returns an array list of all nodes in graph
-- handler.distance(a, b)  -> heuristic function which returns the distance
--                            between node a and node b
-- handler.getNeighbors(n) -> returns an array of all nodes that can be reached
--                            via node n (also called successors of node n)

-- The generic Node class provided (see node.lua) should also be implemented
-- through the handler. Basically, it should describe how nodes are labelled
-- and tested for equality for a custom search space.
-- The following functions should be implemented:
-- function Node:initialize(...) -> creates a Node with custom attributes
-- function Node:isEqualTo(n)    -> returns if self is equal to node n
-- function Node:toString()      -> returns a unique string representation of
--                                  the node, for debug purposes

-- See custom handlers for reference (*_hander.lua).

-- Dependencies
local class = require 'utils.class'
local bheap = require 'utils.bheap'

-- Clears nodes data between consecutive path requests.
local function resetForNextSearch(dijkstra)
for node in pairs(dijkstra.visited) do
node.previous = nil
node.distance = math.huge
end
dijkstra.Q:clear()
dijkstra.visited = {}
end

-- Builds and returns the path to the goal node
local function backtrace(node)
local path = {}
repeat
table.insert(path, 1, node)
node = node.previous
until not node
return path
end

-- Initializes Dijkstra search with a custom handler
local Dijkstra = class()
function Dijkstra:initialize(handler)
self.handler = handler
self.Q = bheap()
self.visited = {}
end

-- Processes the graph for shortest paths
-- source  : the starting node from which the search will spread
-- target  : the goal location. If passed, returns the shortest path from
--  source to this target. If not given, will evaluate all the shortest
--  paths length from to source to all nodes in the graph. This length can
--  be retrieved by indexing in each node after the search (node.distance)
-- Returns : an array of nodes (if target supplied)
function Dijkstra:process(source, target)
resetForNextSearch(self)

source.distance = 0
self.visited[source] = true

local nodes = self.handler.getAllNodes()
for _, node in ipairs(nodes) do self.Q:push(node) end

while not self.Q:isEmpty() do
local u = self.Q:pop()
if u == target then return backtrace(u) end
if u.distance == math.huge then break end
local neighbors = self.handler.getNeighbors(u)
for _, v in ipairs(neighbors) do
local alt = u.distance + self.handler.distance(u, v)
if alt < v.distance then
v.distance = alt
v.previous = u
self.visited[v] = true
self.Q:sort(v)
end
end
end
end

return Dijkstra
``````
``````-- Tests for dijkstra.lua
local Dijkstra = require 'dijkstra'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function same(t, p, comp)
for k,v in ipairs(t) do
if not comp(v, p[k]) then return false end
end
return true
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing linear graph', function()
local comp = function(a, b) return a.value == b end
local ln_handler = require 'handlers.linear_handler'
ln_handler.init(1,5)
local dijkstra = Dijkstra(ln_handler)

local source, dest = ln_handler.getNode(1), ln_handler.getNode(5)
assert(same(dijkstra:process(source, dest), {1,2,3,4,5}, comp))

dijkstra:process(source)
assert(ln_handler.getNode(1).distance == 0)
assert(ln_handler.getNode(2).distance == 1)
assert(ln_handler.getNode(3).distance == 2)
assert(ln_handler.getNode(4).distance == 3)
assert(ln_handler.getNode(5).distance == 4)
end)

run('Testing grid graph', function()
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
local gm_handler = require 'handlers.gridmap_handler'
local dijkstra = Dijkstra(gm_handler)
local map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
gm_handler.init(map)
gm_handler.diagonal = false

local source, dest = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
assert(same(dijkstra:process(source, dest), {{1,1},{1,2},{1,3},{2,3},{3,3},{4,3},{5,3}}, comp))
gm_handler.diagonal = true
assert(same(dijkstra:process(source, dest), {{1,1},{1,2},{2,3},{3,3},{4,3},{5,3}},       comp))
end)

run('Testing point graph', function()
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
local pg_handler = require 'handlers.point_graph_handler'

local dijkstra = Dijkstra(pg_handler)

local comp = function(a, b) return a.name == b end
local source, dest = pg_handler.getNode('a'), pg_handler.getNode('d')
assert(same(dijkstra:process(source, dest),{'a','d'}, comp))

pg_handler.setEdgeWeight('a', 'd', 40)
assert(same(dijkstra:process(source, dest),{'a','b','c', 'd'}, comp))

pg_handler.setEdgeWeight('a', 'b', 6)
assert(same(dijkstra:process(source, dest),{'a','f','e', 'd'}, comp))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````