6.4.2.2 Floyd 算法

教材导航 · 第6章

原书定位

印刷页P236起,对应PDF第248页。下文为目视整理的知识提要;完整内容见原书对照。

按顺序允许顶点 kk 作为中间点,对所有 i,ji,j 更新:

D[i][j]←min⁡(D[i][j],D[i][k]+D[k][j])D[i][j]\leftarrow\min(D[i][j],D[i][k]+D[k][j])

三重循环中 kk 在最外层。初始化对角为 0,直接边为其权,无边为无穷。时间 O(n3)O(n^3),距离矩阵空间 O(n2)O(n^2);可另存中转点或下一跳恢复路径。

允许负边,但不能对受负环影响的端点给出有限最短距离。实现时应避免无穷与数值相加导致溢出。普通矩阵幂统计路径条数,与此处最小值加法递推不同。

Floyd 示例图及初始矩阵

Floyd 示例图及初始矩阵,原书P236。

Floyd 逐轮距离矩阵

Floyd 逐轮距离矩阵,原书P237。

三种最短路径算法比较

三种最短路径算法比较,原书P237。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P236,PDF第248页

原书对照,原书P237,PDF第249页