介绍

Floyd-Warshall 算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall 算法的时间复杂度为$O(N^{3})$，空间复杂度为$O(N^{2})$。

原理

Floyd-Warshall 算法的原理是动态规划。设 $D_{i, j, k}$ 为从 $i$ 到 $j$ 的只以 $(1 . . k)$ 集合中的节点为中间节点的最短路径的长度。

• 若最短路径经过点 $\mathrm{k}$, 则 $D_{i, j, k}=D_{i, k, k-1}+D_{k, j, k-1}$;
• 若最短路径不经过点 k, 则 $D_{i, j, k}=D_{i, j, k-1}$ 。

因此，$D_{i, j, k}=\min \left(D_{i, j, k-1}, D_{i, k, k-1}+D_{k, j, k-1}\right)$ 。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

动态规划

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

算法描述

Floyd-Warshall 算法的伪代码描述如下：

// let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if

其中 dist[i][j] 表示由点 i 到点 j 的代价，当其为 ∞ 表示两点之间没有任何连接。

演示

实现

JavaScript

/*
  Source:
    https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

  Complexity:
    O(|V|^3) where V is the set of vertices
*/

const FloydWarshall = (dist) => {
  // Input:- dist: 2D Array where dist[i][j] = edge weight b/w i and j
  // Output:- dist: 2D Array where dist[i][j] = shortest dist b/w i and j
  const n = dist.length
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          // dist from i to j via k is lesser than the current distance
          dist[i][j] = dist[i][k] + dist[k][j]
        }
      }
    }
  }
  return dist
}

// For the following graph (edge weights are shown in brackets)
//  4       1       dist[1][2] = dist[2][1] = 1
//   \  (2)/ \      dist[1][3] = dist[3][1] = 2
//    \   /   \(1)  dist[1][4] = dist[4][1] = Infinity
//  (1)\ /     \    dist[3][4] = dist[4][3] = 1
//      3       2   dist[2][4] = dist[4][2] = Infinity
//                  dist[2][3] = dist[3][2] = Infinity
// Output should be:
// [ [0, 1, 2, 3],
//   [1, 0, 3, 4],
//   [2, 3, 0, 1],
//   [3, 4, 1, 0] ]

// FloydWarshall(
//     [[0, 1, 2, Infinity],
//       [1, 0, Infinity, Infinity],
//       [2, Infinity, 0, 1],
//       [Infinity, Infinity, 1, 0]
//     ]
//   )

注意：

• 不需要 startNode。

参考

• Floyd–Warshall algorithm - Wikiwand (opens new window)
• Floyd-Warshall 算法 - Wikiwand (opens new window)