Floyd 算法

Floyd 算法

簡介

  • Floyd 算法又稱為插點(diǎn)法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，與 Dijkstra 算法類似。

  • 該算法名稱以創(chuàng)始人之一、1978 年圖靈獎獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特 · 弗洛伊德命名。

核心思路

路徑矩陣

  • 通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣。
  • 從圖的帶權(quán)鄰接矩陣 A=[a(i,j)] n×n 開始，遞歸地進(jìn)行 n 次更新，即由矩陣 D(0)=A，按一個公式，構(gòu)造出矩陣 D(1)；又用同樣地公式由 D(1) 構(gòu)造出 D(2)；……；最后又用同樣的公式由 D(n-1) 構(gòu)造出矩陣 D(n)。矩陣 D(n) 的 i 行 j 列元素便是 i 號頂點(diǎn)到 j 號頂點(diǎn)的最短路徑長度，稱 D(n) 為圖的距離矩陣，同時還可引入一個后繼節(jié)點(diǎn)矩陣 path 來記錄兩點(diǎn)間的最短路徑。
  • 采用松弛技術(shù)（松弛操作），對在 i 和 j 之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時間復(fù)雜度為 O(n^3)。

狀態(tài)轉(zhuǎn)移方程

  • path[i,j]:=min{path[i,k]+path[k,j],path[i,j]}

算法描述

  1. 從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。

  2. 對于每一對頂點(diǎn) u 和 v，看看是否存在一個頂點(diǎn) w （一般稱為中間點(diǎn)）使得從 u 到 w 再到 v 比已知的路徑更短。如果是，更新它（專業(yè)術(shù)語為：松弛）。

  3. 遍歷直到結(jié)束，這時候存儲圖的數(shù)據(jù)結(jié)構(gòu)就得到了多源最短路徑。

優(yōu)缺點(diǎn)分析

  • Floyd 算法適用于 APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行 | V | 次 Dijkstra 算法，也要高于執(zhí)行 | V | 次 SPFA 算法。

    稠密圖定義：邊的條數(shù) | E | 接近 | V|2，稱為稠密圖（dense graph）

  • 優(yōu)點(diǎn)：容易理解，可以算出任意兩個節(jié)點(diǎn)之間的最短距離，代碼編寫簡單。

  • 缺點(diǎn)：時間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。時間復(fù)雜度 O（n^3）,空間復(fù)雜度 O（n^2）。

Python 代碼實(shí)現(xiàn)

  • 代碼：

      import copy
  M=1000000
  def Floyd(G):
      n=len(G)
      path=copy.deepcopy(G)
      for k in range(0,n):
          for i in range(0,n):
              for j in range(0,n):
                  print("Comparing path[%s][%s] and {path[%s][%s]+path[%s][%s]}"%(i,j,i,k,k,j))
                  print("Former path[%s][%s] = %s"%(i,j,path[i][j]))
                  path[i][j]=min(path[i][j],path[i][k]+path[k][j])
                  print("Present path[%s][%s] = %s\n"%(i,j,path[i][j]))
      return path

  if __name__=='__main__':
      G=[
          [0,30,15,M,M,M],
          [5,0,M,M,20,30],
          [M,10,0,M,M,15],
          [M,M,M,0,M,M],
          [M,M,M,10,0,M],
          [M,M,M,30,10,0]
          ]
      print("---------------Floyd----------------")
      path=Floyd(G)
      print("Graph = ")
      for i in range(0,len(G)):
          print (path[i])

代碼詳解

  • 引入 copy ，定義無窮值，在 Python 里還有種寫法： M = float('inf')

  • 定義 Floyd 函數(shù)，參數(shù)為圖的鄰接矩陣 G，在里面首先利用 copy 函數(shù)復(fù)制一份，不復(fù)制的話，會導(dǎo)致兩個變量指向同一個地址（鄰接矩陣）

  • 三重 for 循環(huán)，很容易理解

  • if __name__=='__main__'

    不理解的復(fù)制這段代碼，百度谷歌

測試

  • 還是拿我的另一篇文章 Dijkstra 算法 中的測試用例

  • 鄰接矩陣：

          G=[
          [0,30,15,M,M,M],
          [5,0,M,M,20,30],
          [M,10,0,M,M,15],
          [M,M,M,0,M,M],
          [M,M,M,10,0,M],
          [M,M,M,30,10,0]
          ]

  • 表示的圖如下：

    test

  • 輸出：

    floydtest

小結(jié)

  • 從上面的輸出結(jié)果可以看到 G 矩陣已經(jīng)被更新了

  • 有些走不通的路徑現(xiàn)在可以走通了，因?yàn)樵瓉硎青徑泳仃嚕簝蓚€頂點(diǎn)有鄰接邊，鄰接矩陣對應(yīng)點(diǎn)才有值；現(xiàn)在是整個網(wǎng)絡(luò)，頂點(diǎn) i 到頂點(diǎn) j 如果可達(dá)，那么 G[i][j] 就有值。

  • 但是，我們是得到了兩個點(diǎn)的最小 cost，最短路徑要怎么得到呢？可以再借助一個 path 矩陣，它記錄了中間點(diǎn)的信息，我們可以在最后根據(jù)更新后的 G 矩陣回溯 path 矩陣得到最短路徑。

全局最短路徑的數(shù)據(jù)結(jié)構(gòu)

ShortestPath_dict = {
    0: {1: [0, 2, 1], 2: [0, 2], 3: [0, 2, 5, 4, 3], 4: [0, 2, 5, 4], 5: [0, 2, 5]},
    1: {0: [1, 0], 2: [1, 0, 2], 3: [1, 4, 3], 4: [1, 4], 5: [1, 5]}, 2: {0: [2, 1, 0],
    1: [2, 1], 3: [2, 5, 4, 3], 4: [2, 5, 4], 5: [2, 5]},
    3: {0: [], 1: [], 2: [], 4: [], 5: []},
    4: {0: [], 1: [], 2: [], 3: [4, 3], 5: []},
    5: {0: [], 1: [], 2: [], 3: [5, 4, 3], 4: [5, 4]}
    }
  • 這個數(shù)據(jù)結(jié)構(gòu)利用了字典與列表，其中每兩個頂點(diǎn)的最短路徑用列表表示，如頂點(diǎn) 0 到頂點(diǎn) 1 ：0: {1: [0, 2, 1]，其中的[0, 2, 1]就是最短路徑。

利用 Floyd 得到全局最短路徑

  • 代碼：

      # ------------------函數(shù)-------------------
  def back_path(path,i,j,shortestPath):            #遞歸回溯
      print ("path[%s][%s] = "%(i,j),path[i][j])
      if -1 != path[i][j]:
          shortestPath = back_path(path,i,path[i][j],shortestPath)
          shortestPath = back_path(path,path[i][j],j,shortestPath)
      if j not in shortestPath:
          shortestPath.append(j)
      return shortestPath

  def getShortestPath(graph,path,i,j):
      shortestPath = []
      if graph[i][j] == float('inf') or i == j:
          print("頂點(diǎn)%s 不能到達(dá) 頂點(diǎn)%s！"%(i,j))
          return shortestPath
      elif path[i][j] == -1:
          shortestPath.append(i)
          shortestPath.append(j)
      else :
          shortestPath.append(i)
          shortestPath = back_path(path,i,j,shortestPath)
      print("頂點(diǎn)%s 到 頂點(diǎn)%s 的路徑為："%(i,j),shortestPath)
      return shortestPath

  def getAllShortestPath(graph,path):
      print("------正在生成全局最短路徑------")
      ShortestPath_dict = {}
      for i in range(N):
          ShortestPath_dict[i] = {}
          for j in range(N):
              print("嘗試生成頂點(diǎn)%s到頂點(diǎn)%s的最短路徑..."%(i,j))
              if i !=j :
                  shortestPath = getShortestPath(graph,path,i,j)
                  ShortestPath_dict[i][j] = shortestPath
              print("--------------------------------")
      return ShortestPath_dict

  # ----------------------定義--------------------
  M=float('inf')      #無窮大
  graph = [
          [0,30,15,M,M,M],
          [5,0,M,M,20,30],
          [M,10,0,M,M,15],
          [M,M,M,0,M,M],
          [M,M,M,10,0,M],
          [M,M,M,30,10,0]
          ]
  N = len(graph)
  path = []
  for i in range(N):
      path.append([])
      for j in range(N):
          path[i].append(-1)

  print ("Original Graph:\n",graph)
  # -----------------Floyd Algorithm----------------
  for k in range(N):
      for i in range(N):
          for j in range(N):
              if graph[i][j] > graph[i][k] + graph[k][j]:
                  graph[i][j] = graph[i][k] + graph[k][j]
                  path[i][j] = k

  print ("Shortest Graph:\n",graph)
  print ("Path:\n",path)

  print("ShortestPath =\n",getAllShortestPath(graph,path))

測試2

  • 鄰接矩陣如上所示

  • 表示的圖也如上所示

  • 截圖

    test3

    last

代碼詳解2

  • 在三重循環(huán)階段，與前文第一種做法不同的是：每次還加入了path[i][j] = k，這樣每次松弛，都會被記錄在 path 矩陣中

  • path 矩陣完成后，如測試2中的截圖所示

  • getAllShortestPath 函數(shù)

    • 構(gòu)造字典 ShortestPath_dict
    • 兩兩遍歷圖中各點(diǎn)，循環(huán)調(diào)用 getShortestPath 函數(shù)

  • getShortestPath 函數(shù)

    • 如果兩個頂點(diǎn)不可達(dá)或者這兩個頂點(diǎn)為同一個頂點(diǎn)，那么直接說明不可達(dá)，且返回值為空列表：[]
    • 如果兩個頂點(diǎn)不需要松弛就可以得到最短路徑，那么在 path 矩陣中對應(yīng)點(diǎn)的值就為初始值 -1，這代表了這兩個頂點(diǎn)鄰接，在 getShortestPath 函數(shù)中是需要判斷的
    • 如果兩個頂點(diǎn)需要松弛才能得到最短路徑，那么在 path 矩陣中對應(yīng)點(diǎn)的值就不為 -1，那么需要遞歸調(diào)用 back_path 函數(shù)

  • back_path 函數(shù)

    • 之前說了，path 矩陣中記錄的是每次松弛操作時的中間點(diǎn)，所以在函數(shù)中前后兩次調(diào)用本身

  • 舉例說明

    • 以測試2的截圖為例，嘗試頂點(diǎn)0到頂點(diǎn)3的最短路徑：
      • 進(jìn)入 getShortestPath(graph,path,i,j) ，調(diào)用 back_path(path,0,3,[0])
      • 首先調(diào)用 back_path(path,0,3,[0]) ，發(fā)現(xiàn) path[0][3]=5，說明需要頂點(diǎn)5的中轉(zhuǎn)
      • 于是調(diào)用 back_path(path,0,5,[0]) ，發(fā)現(xiàn) path[0][5]=2，說明需要頂點(diǎn)2的中轉(zhuǎn)
      • 繼續(xù)調(diào)用 back_path(path,0,2,[0]) ，發(fā)現(xiàn)到頭了，頂點(diǎn)0和頂點(diǎn)2直接鄰接，于是不再遞歸下去了，添加頂點(diǎn)2到最短路徑 shortestPath，此時 [0,2]
      • 返回上層，調(diào)用 back_path(path,2,5,[0,2]) ，發(fā)現(xiàn)到頭了，頂點(diǎn)2和頂點(diǎn)5直接鄰接，于是不再遞歸下去了，添加頂點(diǎn)5到最短路徑 shortestPath，此時 [0,2,5]
      • 返回上層，調(diào)用 back_path(path,5,3,[0,2,5])，發(fā)現(xiàn)需要頂點(diǎn)4的中轉(zhuǎn)
      • 于是調(diào)用 back_path(path,5,4,[0,2,5])，發(fā)現(xiàn)到頭了，不再遞歸，添加頂點(diǎn)4到最短距離，此時 [0,2,5,4]
      • 返回上層，調(diào)用 back_path(path,4,3,[0,2,5,4])，發(fā)現(xiàn)到頭了，不再遞歸，添加頂點(diǎn)3到最短距離，此時 [0,2,5,4,3] 已經(jīng)是最短距離了
      • 注意：因?yàn)橹灰{(diào)用 back_path 就會添加頂點(diǎn)進(jìn)入最短路徑 shortestPath，為了避免重復(fù)，加入了 if 判斷，直接過濾掉重復(fù)的頂點(diǎn)，因?yàn)樽疃搪窂讲豢赡芾@圈子。

源碼地址：https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/ShortestPath/floyd.py

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容