Search Algorithms

function dijkstra(initalNode, nodeList, neighborList, destinationNode)
    local unvisited = {}
    local visited = {}
    local previous = {}
    local currentNode = initalNode
    for i,v in ipairs(nodeList) do
        unvisited[v] = 999999999
    end
    unvisited[initalNode] = 0
    while true do
        local distance = unvisited[currentNode]
        for i,v in pairs(neighborList[currentNode]) do
            if unvisited[i] then
                if (distance + v) < unvisited[i] then
                    unvisited[i] = distance+v
                    previous[i] = currentNode
                end
            end
        end
        visited[currentNode] = unvisited[currentNode]
        unvisited[currentNode] = nil
        if destinationNode then
            if visited[destinationNode] then
                break
            end
        end
        local smallest = {999999999, -1}
        for i,v in pairs(unvisited) do
            if v < smallest[1] then
                smallest = {v, i}
            end
        end
        if smallest == {999999999, -1} then
            break
        end
        currentNode = smallest[2]

    end
    return visited, previous
end

function BFS(initalNode, nodeList, neighborList, destinationNode)
    local function splitTable(input) -- splits a table into two, one with indexes, one with values.
        local indexes = {}
        local values = {}
        for i,v in pairs(input) do
            table.insert(indexes, i)
            table.insert(values, v)
        end
        return indexes, values
    end
    local parents = {}
    local queue = {}
    table.insert(queue, initalNode)
    while true do
        if #queue == 0 then
            break
        end
        local node = table.remove(queue, 1)
        if node == destinationNode then
            break
        end
        local nodeNeighbors = splitTable(neighborList[node])
        for i,v in ipairs(nodeNeighbors) do
            table.insert(queue, v)
            parents[v] = node
        end
    end
    return parents
end

function generatePath(initalNode, nodeList, neighborList, destinationNode, useBFS)
    local distances = {}
    local links = {}
    if useBFS then
        links = BFS(initalNode, nodeList, neighborList, destinationNode)
    else
        distances, links = dijkstra(initalNode, nodeList, neighborList, destinationNode)
    end
    local stack = {}
    local current = destinationNode
    while true do
        table.insert(stack, 1, current)
        if links[current] then
            current = links[current]
        else
            break
        end
    end
    return stack
end