算法原理
- 保存兩個(gè)數(shù)組S和U棒动，S用于存放已經(jīng)找到和起點(diǎn)之間最短距離的點(diǎn)，U用于存放尚未找到最短距離的點(diǎn)叨叙，起初S中只有起點(diǎn)锭弊，其余所有的點(diǎn)存放在U中，并根據(jù)和起點(diǎn)是否相鄰擂错，修改了距離起點(diǎn)的距離味滞，不相鄰則默認(rèn)為無窮遠(yuǎn)。
- 循環(huán)遍歷U中的點(diǎn)，找出離起點(diǎn)距離最近的點(diǎn)剑鞍，該點(diǎn)到起點(diǎn)的距離就是該點(diǎn)到起點(diǎn)的最短距離昨凡，將該點(diǎn)從U中移除并放置到S中去，并重新計(jì)算U中的點(diǎn)距離起點(diǎn)的距離蚁署。這樣每次選取的點(diǎn)都是剩余點(diǎn)中距離起點(diǎn)最近的點(diǎn)便脊。
- 循環(huán)上述操作，直到找到終點(diǎn)到起點(diǎn)的最短路徑或則循環(huán)結(jié)束光戈。
通俗解釋
算法每次都查找距離起始點(diǎn)最近的點(diǎn)哪痰，那么剩下的點(diǎn)距離起始點(diǎn)的距離一定比當(dāng)前點(diǎn)大。
圖解
1.選定A節(jié)點(diǎn)并初始化久妆，如上述步驟3所示
image
2.執(zhí)行上述 4晌杰、5兩步驟，找出U集合中路徑最短的節(jié)點(diǎn)D 加入S集合筷弦，并根據(jù)條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合
image
3.這時(shí)候 A->B, A->C 都為3肋演，沒關(guān)系。其實(shí)這時(shí)候他倆都是最短距離烂琴，如果從算法邏輯來講的話惋啃，會(huì)先取到B點(diǎn)。而這個(gè)時(shí)候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) 监右，如圖所示這時(shí)候A->B距離 其實(shí)為 A->D->B
image
思路就是這樣，往后就是大同小異了
算法結(jié)束
Dijkstra算法的探測(cè)過程
image
（圖片來源于網(wǎng)絡(luò)）
Dijkstra算法保證能找到一條從初始點(diǎn)到目標(biāo)點(diǎn)的最短路徑异希，只要所有的邊都有一個(gè)非負(fù)的代價(jià)值健盒。在上圖中，粉紅色的結(jié)點(diǎn)是初始結(jié)點(diǎn)称簿，藍(lán)色的是目標(biāo)點(diǎn)扣癣，而類菱形的有色區(qū)域則是Dijkstra算法掃描過的區(qū)域。顏色最淡的區(qū)域是那些離初始點(diǎn)最遠(yuǎn)的憨降，因而形成探測(cè)過程（exploration）的邊境（frontier）父虑。因而Dijkstra算法可以找到一條最短的路徑，但是效率上并不高授药。
lua代碼實(shí)現(xiàn)
- 點(diǎn)的數(shù)據(jù)結(jié)構(gòu)的定義
--[[
-- Dijkstra算法中需要的點(diǎn)的信息結(jié)構(gòu)
]]
local MAX_DISTANCE = 999999999999999999
---------------------------------------------------------------------------------------------
-------------------------------- 相鄰的點(diǎn)的結(jié)構(gòu) -----------------------------------
---------------------------------------------------------------------------------------------
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
---------------------------------------------------------------------------------------------
------------------------------- 點(diǎn)的結(jié)構(gòu) --------------------------------------
local DijkstraPointObj = ns.class("DijkstraPointObj")
function DijkstraPointObj:ctor(pointIdx,links)
ns.utils.registerVariableAndSetGetFunc(self,"pointIdx", pointIdx or 0) -- 點(diǎn)的索引
ns.utils.registerVariableAndSetGetFunc(self, "links", links or {}) -- 相鄰的點(diǎn)的集合
ns.utils.registerVariableAndSetGetFunc(self,"distance", MAX_DISTANCE) -- 用于輔助算法記錄距離起點(diǎn)的距離的
ns.utils.registerVariableAndSetGetFunc(self,"routes", {}) -- 記錄距離起點(diǎn)的過程中經(jīng)過的點(diǎn)
end
function DijkstraPointObj:initWithParams(pointIdx, links)
self._pointIdx = pointIdx
self._links = links or {}
return self
end
--[[
-- 添加一個(gè)相鄰的點(diǎn)
]]
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
--[[
-- 獲取兩個(gè)頂點(diǎn)之間的距離
-- 如果相鄰士嚎，返回之間的實(shí)際距離，否則返回?zé)o窮大
]]
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
--[[
-- 判斷距離是否時(shí)無窮遠(yuǎn)
]]
function DijkstraPointObj:isValidDistance()
local distance = self:getDistance()
return distance < MAX_DISTANCE
end
return DijkstraPointObj
- 算法代碼的實(shí)現(xiàn)
--[[
-- 最短路徑算法
]]
local DijkstraCommand = ns.class("DijkstraCommand")
function DijkstraCommand:ctor(points)
self._points = points or {}
self._recordMap = {} -- 將所有計(jì)算出最短路徑信息全部記錄下來悔叽，便于后續(xù)使用
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
--[[
-- 查找是否已經(jīng)有記錄了
]]
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
--[[
-- 開始查找,并將查找到的路徑轉(zhuǎn)換成點(diǎn)的數(shù)組的形式
]]
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
--[[
-- 開始尋找動(dòng)作
-- @beginIdx：起點(diǎn)
-- @endIdx: 終點(diǎn)
-- @points:所有的點(diǎn)的列表莱衩，DijkstraPointObj對(duì)象的列表
]]
function DijkstraCommand:start(beginIdx,endIdx,points)
ns.logW(string.format("DijkstraCommand尋路：起點(diǎn) = %d, 終點(diǎn) = %d",beginIdx,endIdx))
if beginIdx == endIdx then
return {},0
end
points = points or self._points
-- 檢查記錄中是否已經(jīng)查到該點(diǎn)
local routes,distance = self:findRecord(beginIdx,endIdx)
if routes then
return routes,distance
end
local S = {} -- 已經(jīng)遍歷過的節(jié)點(diǎn)
local U = {} -- 尚未遍歷的節(jié)點(diǎn)
-- 將起始點(diǎn)放置到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
-- 將剩余的點(diǎn)全部防止到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中的點(diǎn)按照到beginPointObj的距離從近到遠(yuǎn)排列
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)
-- 選擇距離最近的(距離不是無窮遠(yuǎn)的點(diǎn))，添加到S中去娇澎，并從U中移除
local pointObj = U[1]
if pointObj and pointObj:isValidDistance() then
table.insert(S,pointObj)
table.remove(U,1)
-- 判斷是是否時(shí)終點(diǎn)
if pointObj:getPointIdx() == endIdx then
ns.logW("DijkstraCommand找到結(jié)果")
return pointObj:getRoutes(), pointObj:getDistance()
end
-- 更新U中其他的距離S點(diǎn)的距離（相對(duì)于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未找到結(jié)果 pointId = ",pointObj:getPointIdx()))
return {},0
end
end
return {},0
end
return DijkstraCommand
