弗洛伊德算法

维基百科,自由的百科全书
跳转至: 导航搜索
弗洛伊德算法
分類 全局最短路径问题(适用于带权图)
數據結構
最差時間複雜度 O(|V|^3)
最優時間複雜度 \Omega (|V|^3)
最差空間複雜度 \Theta(|V|^2)

Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正確處理有向圖或负权的最短路径問題,同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度O(N^3)空间复杂度O(N^2)

原理[编辑]

Floyd-Warshall算法的原理是动态规划

D_{i,j,k}为从ij的只以(1..k)集合中的节点为中间節点的最短路径的长度。

  1. 若最短路径经过点k,则D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}
  2. 若最短路径不经过点k,则D_{i,j,k}=D_{i,j,k-1}

因此,D_{i,j,k}=\mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})

在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。(见下面的算法描述)

算法描述[编辑]

Floyd-Warshall算法的描述如下:

for k  1 to n do
  for i  1 to n do
    for j  1 to n do
      if (D_{i,k} + D_{k,j} < D_{i,j}) then
        D_{i,j}  D_{i,k} + D_{k,j};

其中D_{i,j}表示由點i到點j的代價,當D_{i,j}為 ∞ 表示兩點之間沒有任何連接。

请参阅[编辑]