Floyd

yyycj · 2025-07-30 23:23:49 · 算法·理论

Floyd 是一种求最短路的算法，并且支持负边权，时间复杂度为 O(n^{3})，与 Dijkstra 和 SPFA 不同的是，Floyd 可以求出全源最短路。本质是 dp，而 dp 有状态定义，转移方程，初始化，答案。

1. 状态定义：定义 dp_{k,i,j} 表示只考虑前 k 个点，从 i 到 j 的最短路。

2. 转移方程：dp_{k,i,j}=\min(dp_{k,i,j},dp_{k,i,k}+dp_{k,k,j})，由于 dp_{k-1,i,j} 和 dp_{k,i,j} 只有多了点 k 的区别，所以我们就判断让点 k 作为中转站的路径是否小于原路径。

3. 初始化：如果 i 到 j 有边，那么 dp_{0,i,j}=w_{i,j}，否则为正无穷；如果 i=j，那么 dp_{0,i,j}=0。

4. 答案：dp_{n,i,j} 表示 i 到 j 的最短路。

不难发现第一维是可以直接压缩掉的

代码：

memset(dp, INT_INF, sizeof dp);
for (int i = 1; i <= n; i++) dp[i][i] = 0;
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]);
    }
  }
}