算法原理
- 保存两个数组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
网友评论