公告
欢迎来到我的博客喵。
509 字
3 分钟
Floyd-Warshall算法
给定一个有向加权图G=(V,E)，其中V是顶点集合，E是边集合，w(u,v)表示边(u,v)的权重。
问题：计算 ，从 到 的最短路径。
限制条件：图中可能存在负权边，但不允许存在负权回路。
算法思想
Floyd-Warshall算法是一种动态规划算法， 可达 ，说明有路，最短路径可以通过引入中间节点来逐步优化。
TIP不同于Djikstra算法的贪心策略，Djikstra算法访问节点的邻居，Floyd-Warshall算法通过逐步引入中间节点，考虑所有可能的路径组合，从而找到全局最短路径。
从路径 ，不断考虑新加入的节点 可以得到以下转移方程：
\min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1}) && if\;\; k \ge 1 \\ w(i,j) && if\;\; k = 0 \;\; and\;\; (i,j) \in E \\ \end{cases} $$ 其中，$d_{ij}^k$ 表示编号不大于 $k$ 的从 $v_i$ 到 $v_j$ 的最短路径长度，$d_{ik}^k$ 表示从 $v_i$ 到 $v_k$ 的最短路径长度，$d_{kj}^k$ 表示从 $v_k$ 到 $v_j$ 的最短路径长度。 ## 算法数据结构 采用**邻接矩阵** $C$ 表示图 $G$ 采用二维数组 $D[n][n]$，其中 $D[i][j]$ 表示从节点 $v_i$ 到节点 $v_j$ 的最短路径长度。 维护一个二维数组 $P[n][n]$，用于记录路径信息，$P[i][j]$ 表示从节点 $v_i$ 到节点 $v_j$ 的最短路径上，$v_j$ 的**前一个节点**。 ## 算法步骤 1. 初始化： - 创建邻接矩阵 $C$，如果边 $(i,j) \in E$，则 $C[i][j] = w(i,j)$，否则 $C[i][j] = \infty$。对于所有节点 $i$，设置 $C[i][i] = 0$。 - 初始化二维数组 $D$，令 $D[i][j] = C[i][j]$。 - 初始化路径数组 $P$，如果 $(i,j) \in E$ 且 $i \neq j$，则设置 $P[i][j] = i$，否则设置 $P[i][j] = -1$。 2. 主循环： - 对于每个中间节点 $k \in V$，更新所有节点对 $(i,j)$ 的最短路径：D[i] [j] = \min(D[i] [j], D[i] [k] + D[k] [j])
\text{if } D[i] [j] = D[i] [k] + D[k] [j] \text{ then } P[i] [j] = P[k] [j]=k
Floyd-Warshall算法
https://biscuit0613.github.io/posts/algorithm/floyd-warshall/