算法思想
Floyd算法是一種動(dòng)態(tài)規(guī)劃算法勒奇，查找i到j(luò)之間的最短距離,我們可以找一個(gè)中間點(diǎn)k,然后變成子問題,i到k的最短路徑和k到j(luò)的最短路徑尖坤。也就是說,我們可以枚舉中間點(diǎn)k,找到最小的d[i][k]+d[k][j],作為d[i][j]的最小值。
Floyd構(gòu)造的結(jié)構(gòu)非常巧妙：找i和j之間通過編號(hào)不超過k（k從1到n）的節(jié)點(diǎn)的最短路徑（一定要注意焊唬，這里是當(dāng)前最短路徑媒惕，當(dāng)k=n時(shí)達(dá)到最終最短路徑）拼苍。為了便于說明贬芥，我們可以弄一個(gè)三維數(shù)組f[k][i][j]表示i和j之間可以通過編號(hào)不超過k的節(jié)點(diǎn)的“最短路徑”吐辙。對(duì)于k-1到k，只有兩種可能蘸劈，經(jīng)過編號(hào)為k的點(diǎn)昏苏，要么不能找到一條從i到j(luò)的更短路，此時(shí)有f[k][i][j] = f[k-1][i][j] 威沫；要么能找到贤惯，那這個(gè)最短路徑一定是d[i][k]+d[k][j]，那么就用這個(gè)較小的距離去更新d[i][j]棒掠。綜合以上兩種情況孵构，f[k][i][j] = min(f[k-1][i][j] , f[k-1][i][k]+f[k-1][k][j])
動(dòng)態(tài)轉(zhuǎn)移推導(dǎo)（重要）
- 動(dòng)態(tài)轉(zhuǎn)移思想可以認(rèn)為是在建立一種當(dāng)前狀態(tài)向之前狀態(tài)的轉(zhuǎn)移的方法。
- d[k][i][j]表示使用1號(hào)到K號(hào)的中間點(diǎn)來計(jì)算i到j(luò)直接按的最短距離烟很。
- i和j之間的最短距離有兩種情況颈墅，情況一：最短距離經(jīng)過K點(diǎn)；情況二：最短距離不經(jīng)過k點(diǎn)雾袱。
- 如果i和j之間的最短距離經(jīng)過k點(diǎn)精盅，則D[k,i,j] = D[K,i,j]，否則D[k,i,j] = D[k-1,i,j]谜酒；那么最終的結(jié)果為D[k,i,j] = min(D[k,i,j],D[k-1,i,k]+D[k-1,k,j])。
- 因此可知妻枕，如果i到j(luò)之間的最短距離如果不經(jīng)過k點(diǎn)僻族，則可轉(zhuǎn)移到k-1、k-2... 一直到1屡谐，總是可以將k的狀態(tài)向前轉(zhuǎn)移到上一個(gè)狀態(tài)述么。
- 最后通過k從1到n的遍歷，可最終找到i到j(luò)之間的最短距離愕掏。
- 兩點(diǎn)之間的最短距離如果需要經(jīng)過第三點(diǎn)的話 這個(gè)第三點(diǎn)一定不是起點(diǎn)或終點(diǎn)（這樣的話就是兩點(diǎn)之間的距離是最短距離了）度秘。
- 如果點(diǎn)i和點(diǎn)j之間經(jīng)過k點(diǎn)，則i點(diǎn)和k點(diǎn)之間一定不會(huì)經(jīng)過j 即路徑之間不會(huì)出現(xiàn)相互引用到的情況烙样。
通俗理解
- Floyd算法通過依次修改中間節(jié)點(diǎn)耍共，計(jì)算任意兩點(diǎn)的經(jīng)過中間節(jié)點(diǎn)后的距離，計(jì)算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離粟耻；每次計(jì)算完成的結(jié)果都是當(dāng)前的最優(yōu)解垢乙，當(dāng)所有的中間節(jié)點(diǎn)被遍歷結(jié)束后獲得的結(jié)果就是整個(gè)算法的最優(yōu)解锨咙。
算法步驟分析
（圖片資源來源于網(wǎng)絡(luò)）
image
算法代碼實(shí)現(xiàn)
- 算法中點(diǎn)的定義
--[[
-- Floyd算法中的點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
]]
local max_distance = 9999999999999999999999999999
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 FloydPointObj = ns.class("FloydPointObj")
function FloydPointObj:ctor(pointIdx)
ns.utils.registerVariableAndSetGetFunc(self,"pointIdx", pointIdx or 0) -- 當(dāng)前點(diǎn)的ID
ns.utils.registerVariableAndSetGetFunc(self,"links", {}) -- 當(dāng)前點(diǎn)的所有的相鄰點(diǎn)
end
--[[
-- 添加相鄰點(diǎn)
]]
function FloydPointObj:addLink(pointIdx,distance)
local link = LinkObj.new(pointIdx,distance)
table.insert(self._links,link)
return self
end
--[[
-- 獲取兩個(gè)點(diǎn)是否是相鄰
]]
function FloydPointObj:isLink(pointIdx)
for i = 1,#self._links do
local link = self._links[i]
if link and link:getPointIdx() == pointIdx then
return true
end
end
return false
end
--[[
-- 獲取兩個(gè)點(diǎn)之間的距離，如果兩個(gè)點(diǎn)不相鄰追逮，返回?zé)o窮大
]]
function FloydPointObj:getLinkDistance(pointIdx)
for i = 1,#self._links do
local link = self._links[i]
if link and link:getPointIdx() == pointIdx then
return link:getDistance()
end
end
return max_distance
end
return FloydPointObj
- 算法的實(shí)現(xiàn)
local FloydCommand = ns.class("FloydCommand")
function FloydCommand:ctor()
self._D = {} -- 存放最短距離的二維數(shù)組
self._P = {} -- 存放最短路徑經(jīng)過的點(diǎn)的二維數(shù)據(jù)
end
--[[
-- 計(jì)算出所有的點(diǎn)之間的最短距離的數(shù)組
]]
function FloydCommand:execute(floydPointObjs)
local points = floydPointObjs or {}
local pointNums = #points
local D = self._D
local P = self._P
-- 初始化距離數(shù)組和最短路徑經(jīng)過的點(diǎn)的數(shù)組
for i =1,pointNums do
local pointObj = points[i]
local subDisTab = {}
local subPointTab = {}
for j = 1,pointNums do
local subPointObj = points[j]
local distance = pointObj:getLinkDistance(subPointObj:getPointIdx())
table.insert(subDisTab,distance)
table.insert(subPointTab,{pointObj:getPointIdx()})
end
table.insert(D,subDisTab)
table.insert(P,subPointTab)
end
-- 開始執(zhí)行算法核心循環(huán)
for k = 1,pointNums do -- 該層循環(huán)用于計(jì)算所有的點(diǎn)之間經(jīng)過該點(diǎn)之后的距離是否是最短距離
for i = 1,pointNums do
for j = 1,pointNums do
local distance = D[i][k] + D[k][j]
if D[i][j] > distance then
D[i][j] = distance
local points = ns.clone(P[i][k])
table.insertto(points,ns.clone(P[k][j]))
P[i][j] = points
end
end
end
end
return self
end
function FloydCommand:find(beginPoint,endPoint)
local distance = self._D[beginPoint][endPoint] or 0
local points = ns.clone(self._P[beginPoint][endPoint] or {})
-- 注意P中的路徑不包括終點(diǎn)酪刀，需要手動(dòng)添加
table.insert(points,endPoint)
return points,distance
end
return FloydCommand
