算法思想

• Floyd算法是一種動態(tài)規(guī)劃算法，查找i到j之間的最短距離,我們可以找一個中間點k,然后變成子問題,i到k的最短路徑和k到j的最短路徑。也就是說,我們可以枚舉中間點k,找到最小的d[i][k]+d[k][j],作為d[i][j]的最小值。

• Floyd構造的結構非常巧妙：找i和j之間通過編號不超過k（k從1到n）的節(jié)點的最短路徑（一定要注意，這里是當前最短路徑，當k=n時達到最終最短路徑）。為了便于說明，我們可以弄一個三維數(shù)組f[k][i][j]表示i和j之間可以通過編號不超過k的節(jié)點的“最短路徑”。對于k-1到k，只有兩種可能，經(jīng)過編號為k的點，要么不能找到一條從i到j的更短路，此時有f[k][i][j] = f[k-1][i][j] ；要么能找到，那這個最短路徑一定是d[i][k]+d[k][j]，那么就用這個較小的距離去更新d[i][j]。綜合以上兩種情況，f[k][i][j] = min(f[k-1][i][j] , f[k-1][i][k]+f[k-1][k][j])

動態(tài)轉移推導（重要）

• 動態(tài)轉移思想可以認為是在建立一種當前狀態(tài)向之前狀態(tài)的轉移的方法。
• d[k][i][j]表示使用1號到K號的中間點來計算i到j直接按的最短距離。
• i和j之間的最短距離有兩種情況，情況一：最短距離經(jīng)過K點；情況二：最短距離不經(jīng)過k點。
• 如果i和j之間的最短距離經(jīng)過k點，則D[k,i,j] = D[K,i,j]，否則D[k,i,j] = D[k-1,i,j]；那么最終的結果為D[k,i,j] = min(D[k,i,j],D[k-1,i,k]+D[k-1,k,j])。
• 因此可知，如果i到j之間的最短距離如果不經(jīng)過k點，則可轉移到k-1、k-2... 一直到1，總是可以將k的狀態(tài)向前轉移到上一個狀態(tài)。
• 最后通過k從1到n的遍歷，可最終找到i到j之間的最短距離。
• 兩點之間的最短距離如果需要經(jīng)過第三點的話 這個第三點一定不是起點或終點（這樣的話就是兩點之間的距離是最短距離了）。
• 如果點i和點j之間經(jīng)過k點，則i點和k點之間一定不會經(jīng)過j 即路徑之間不會出現(xiàn)相互引用到的情況。

通俗理解

• Floyd算法通過依次修改中間節(jié)點，計算任意兩點的經(jīng)過中間節(jié)點后的距離，計算出任意兩個節(jié)點之間的最短距離；每次計算完成的結果都是當前的最優(yōu)解，當所有的中間節(jié)點被遍歷結束后獲得的結果就是整個算法的最優(yōu)解。

算法步驟分析

（圖片資源來源于網(wǎng)絡）

image

算法代碼實現(xiàn)

• 算法中點的定義

--[[
--      Floyd算法中的點的數(shù)據(jù)結構
 ]]
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)  -- 當前點的ID
    ns.utils.registerVariableAndSetGetFunc(self,"links",    {}) -- 當前點的所有的相鄰點
end

--[[
--      添加相鄰點
 ]]
function FloydPointObj:addLink(pointIdx,distance)
    local link = LinkObj.new(pointIdx,distance)

    table.insert(self._links,link)
    return self
end

--[[
--      獲取兩個點是否是相鄰
 ]]
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

--[[
--      獲取兩個點之間的距離，如果兩個點不相鄰，返回無窮大
 ]]
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

• 算法的實現(xiàn)

local FloydCommand = ns.class("FloydCommand")

function FloydCommand:ctor()
    self._D = {}        -- 存放最短距離的二維數(shù)組
    self._P = {}        -- 存放最短路徑經(jīng)過的點的二維數(shù)據(jù)
end

--[[
--      計算出所有的點之間的最短距離的數(shù)組
 ]]
function FloydCommand:execute(floydPointObjs)
    local points    = floydPointObjs or {}
    local pointNums = #points

    local D = self._D
    local P = self._P
    -- 初始化距離數(shù)組和最短路徑經(jīng)過的點的數(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īng)過該點之后的距離是否是最短距離
        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中的路徑不包括終點，需要手動添加
    table.insert(points,endPoint)
    return points,distance
end

return FloydCommand

參考文章

探求Floyd算法的動態(tài)規(guī)劃本質

floyd算法:我們真的明白floyd嗎?