最短路径 - Dijkstra算法

2019-03-28 本文已影响0人 jepsonCheng

算法原理

保存两个数组S和U，S用于存放已经找到和起点之间最短距离的点，U用于存放尚未找到最短距离的点，起初S中只有起点，其余所有的点存放在U中，并根据和起点是否相邻，修改了距离起点的距离，不相邻则默认为无穷远。
循环遍历U中的点，找出离起点距离最近的点，该点到起点的距离就是该点到起点的最短距离，将该点从U中移除并放置到S中去，并重新计算U中的点距离起点的距离。这样每次选取的点都是剩余点中距离起点最近的点。
循环上述操作，直到找到终点到起点的最短路径或则循环结束。

通俗解释

算法每次都查找距离起始点最近的点，那么剩下的点距离起始点的距离一定比当前点大。

图解

1.选定A节点并初始化，如上述步骤3所示

image

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

image

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离其实为 A->D->B

image

思路就是这样，往后就是大同小异了
算法结束

Dijkstra算法的探测过程

image

（图片来源于网络）

Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。在上图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）。因而Dijkstra算法可以找到一条最短的路径，但是效率上并不高。

lua代码实现

点的数据结构的定义

--[[
--     Dijkstra算法中需要的点的信息结构
 ]]

local MAX_DISTANCE = 999999999999999999
---------------------------------------------------------------------------------------------
--------------------------------        相邻的点的结构     -----------------------------------
---------------------------------------------------------------------------------------------
local LinkObj = ns.class("LinkObj")
function LinkObj:ctor(pointIdx, distance)
    ns.utils.registerVariableAndSetGetFunc(self, "pointIdx", pointIdx or 0)
    ns.utils.registerVariableAndSetGetFunc(self, "distance", distance or 0)
end

---------------------------------------------------------------------------------------------
-------------------------------         点的结构        --------------------------------------
local DijkstraPointObj = ns.class("DijkstraPointObj")

function DijkstraPointObj:ctor(pointIdx,links)
    ns.utils.registerVariableAndSetGetFunc(self,"pointIdx", pointIdx or 0)  -- 点的索引
    ns.utils.registerVariableAndSetGetFunc(self, "links",   links or {}) -- 相邻的点的集合



    ns.utils.registerVariableAndSetGetFunc(self,"distance",  MAX_DISTANCE) -- 用于辅助算法记录距离起点的距离的
    ns.utils.registerVariableAndSetGetFunc(self,"routes",    {})   -- 记录距离起点的过程中经过的点
end

function DijkstraPointObj:initWithParams(pointIdx, links)
    self._pointIdx = pointIdx
    self._links    = links or {}

    return self
end

--[[
--      添加一个相邻的点
 ]]
function DijkstraPointObj:addLink(pointIdx,distance)
    local linkObj = LinkObj.new(pointIdx,distance)

    table.insert(self._links,linkObj)
end


--[[
--      判断是否相邻
 ]]
function DijkstraPointObj:isLink(pointIdx)
    local links = self._links or {}
    for i = 1,#links do
        local link = links[i]
        if link and link:getPointIdx() == pointIdx then
            return true
        end
    end

    return false
end

--[[
--      获取两个顶点之间的距离
--          如果相邻，返回之间的实际距离，否则返回无穷大
 ]]
function DijkstraPointObj:getLinkDistance(pointIdx)
    local links = self._links or {}
    for i = 1,#links do
        local link = links[i]
        if link and link:getPointIdx() == pointIdx then
            return link:getDistance()
        end
    end

    return MAX_DISTANCE
end

--[[
--      判断距离是否时无穷远
 ]]
function DijkstraPointObj:isValidDistance()
    local distance = self:getDistance()

    return distance < MAX_DISTANCE
end


return DijkstraPointObj

算法代码的实现

--[[
--       最短路径算法
 ]]

local DijkstraCommand = ns.class("DijkstraCommand")

function DijkstraCommand:ctor(points)
    self._points    = points or {}
    self._recordMap = {}        -- 将所有计算出最短路径信息全部记录下来，便于后续使用
end

--[[
--      将最近路径全部记录下来
 ]]
function DijkstraCommand:recordResult(beginIdx,endIdx,routes,distance)
    local key = string.format("%d_%d",beginIdx,endIdx)

    local info = {
        beginIdx = beginIdx,
        endIdx   = endIdx,
        routes   = routes,
        distance = distance,
    }

    self._recordMap[key] = info
end

--[[
--      查找是否已经有记录了
 ]]

function DijkstraCommand:findRecord(beginIdx,endIdx)
    local firstKey = string.format("%d_%d",beginIdx,endIdx)

    local info = self._recordMap[firstKey]
    if info then
        return info.routes,info.distance
    end

    local secondKey = string.format("%d_%d",endIdx,beginIdx)
    local info = self._recordMap[secondKey]
    if info then
        return table.reverse(info.routes),info.distance
    end

    return nil
end

--[[
--      清空本地的记录
 ]]
function DijkstraCommand:cleanRecord()
    self._recordMap = {}
end


--[[
--      开始查找,并将查找到的路径转换成点的数组的形式
 ]]
function DijkstraCommand:find(beginIdx,endIdx,points)
    local routes,distance = self:start(beginIdx,endIdx,points)
    routes      = routes or {}
    distance    = distance or 0

    local points    = {}
    for i = 1,#routes do
        table.insert(points,routes[i]:getPointIdx())
    end

    return points,distance
end



--[[
--      开始寻找动作
--          @beginIdx：起点
--          @endIdx: 终点
--          @points:所有的点的列表，DijkstraPointObj对象的列表
 ]]
function DijkstraCommand:start(beginIdx,endIdx,points)
    ns.logW(string.format("DijkstraCommand寻路：起点 = %d, 终点 = %d",beginIdx,endIdx))
    if beginIdx == endIdx then
        return {},0
    end

    points = points or self._points

    -- 检查记录中是否已经查到该点
    local routes,distance = self:findRecord(beginIdx,endIdx)
    if routes then
        return routes,distance
    end


    local S = {}    -- 已经遍历过的节点
    local U = {}    -- 尚未遍历的节点

    -- 将起始点放置到S列表中去
    local beginPointObj = nil
    for i = 1,#points do
        local pointObj = points[i]
        local pointIdx = pointObj:getPointIdx()
        if pointIdx == beginIdx then
            table.insert(S,pointObj)
            beginPointObj = pointObj
            break
        end
    end

    if not beginPointObj then
        return {},0
    end

    -- 将剩余的点全部防止到U列表中去
    for i = 1,#points do
        local pointObj = points[i]
        local pointIdx = pointObj:getPointIdx()
        if pointIdx ~= beginIdx then
            local distance = beginPointObj:getLinkDistance(pointIdx)
            pointObj:setDistance(distance)
            pointObj:setRoutes({beginPointObj,pointObj})
            table.insert(U,pointObj)
        end
    end

    while #U > 0 do
        -- 将U中的点按照到beginPointObj的距离从近到远排列
        table.sort(U,function(a,b)
            local distanceA = a:getDistance()
            local distanceB = b:getDistance()
            if distanceA ~= distanceB then
                return distanceA < distanceB
            end

            return a:getPointIdx() < b:getPointIdx()
        end)


        -- 选择距离最近的(距离不是无穷远的点)，添加到S中去，并从U中移除
        local pointObj = U[1]
        if pointObj and pointObj:isValidDistance() then
            table.insert(S,pointObj)
            table.remove(U,1)
            -- 判断是是否时终点
            if pointObj:getPointIdx() == endIdx then
                ns.logW("DijkstraCommand找到结果")
                return pointObj:getRoutes(), pointObj:getDistance()
            end

            -- 更新U中其他的距离S点的距离（相对于pointObj的）
            for i = 1,#U do
                local nextPointObj = U[i]

                if pointObj:isLink(nextPointObj:getPointIdx()) then
                    local distance = pointObj:getLinkDistance(nextPointObj:getPointIdx())
                        + pointObj:getDistance()

                    if distance < nextPointObj:getDistance() then
                        nextPointObj:setDistance(distance)

                        local routes = ns.clone(pointObj:getRoutes())
                        table.insert(routes,nextPointObj)
                        nextPointObj:setRoutes(routes)
                    end
                end
            end
        else
            ns.logW(string.format("DijkstraCommand未找到结果  pointId = ",pointObj:getPointIdx()))
            return {},0
        end
    end

    return {},0
end


return DijkstraCommand

参考文章

数据结构--Dijkstra算法最清楚的讲解

最短路径 - Dijkstra算法

算法原理

通俗解释

图解

Dijkstra算法的探测过程

lua代码实现

参考文章

猜你喜欢

热点阅读