Floyd 算法¶

简介¶

Floyd 算法(1) 是用来求任意两点之间的最短路的，适用于任何无负环等没有最短路的图，并且容易实现，代码短。致命缺点就是复杂度较高，需要 \(\mathcal O(n^3)\) 的时间复杂度和 \(\mathcal O(n^2)\) 的空间复杂度。

Floyd 算法，全名 Floyd-Wallshall，又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与 Dijkstra 算法类似。该算法名称以创始人之一、\(1978\) 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。——百度百科

算法思想¶

设 \(dp_{(k,i,j)}\) 表示为最短路在只经过 \(1\sim k\) 这 \(k\) 个中转结点的前提下，\(i\) 到 \(j\) 的最短距离，那么很简单，\(i\) 到 \(j\) 的最短距离我们就尝试加入中转结点 \(k\)，也就是把 \(i\sim k\) 和 \(k\sim j\) 的路径给拼起来，然后与当前 \(i\sim j\) 的路径做比较，取最小值。状态转移方程就是 \(dp_{(k,i,j)}=\min(dp_{(k-1,i,j)},dp_{(k-1,i,k)}+dp_{(k-1,k,j)})\)。

然后我们发现，其实每一次我们都从 \(k-1\) 转移了所有状态到 \(k\)，那么其实我们可以直接原地修改（压数组），或者按照之前动态规划里面讲解的滚动数组进行优化，那么空间复杂度就可以降成 \(\mathcal O(n^2)\)。

注意如果这一个图是双向图的话，那么 \(i\) 到 \(j\) 的距离和 \(j\) 到 \(i\) 的距离是一样的，因此我们就可以进行优化，省去一半的时间复杂度。

代码

普通 Floyd加入压数组优化

for (int k = 1; k <= n; k++) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
    }
  }
}

for (int k = 1; k <= n; k++) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }
  }
}

传递闭包¶

问题

给出一个图和若干个询问，每一个询问都问你指定两点能否直接或间接到达。

我们还是采用 Floyd 的思想，把最短路数组改成 bool 数组，如果 \(i\) 和 \(j\) 可以到达，那么 \(dp_{(i,j)}=1\)，然后把 Floyd 的取最小值改成逻辑或运算就行了。

事实上，我们还可以使用 std::bitset 进行优化，然后对一整个数组全部进行或运算，那么时间复杂度就变成了 \(\mathcal O(\cfrac{n^3}{w})\)。'

代码

bitset<kMaxN> dp[kMaxN];
for (int k = 1; k <= n; k++) {
  for (int i = 1; i <= n; i++) {
    if (dp[i][k]) {
      dp[i] |= dp[k];
    }
  }
}

Floyd 算法¶

简介¶

算法思想¶

传递闭包¶

评论