6.4.2.2 Floyd 算法
原书定位
印刷页P236起,对应PDF第248页。下文为目视整理的知识提要;完整内容见原书对照。
按顺序允许顶点 作为中间点,对所有 更新:
三重循环中 在最外层。初始化对角为 0,直接边为其权,无边为无穷。时间 ,距离矩阵空间 ;可另存中转点或下一跳恢复路径。
允许负边,但不能对受负环影响的端点给出有限最短距离。实现时应避免无穷与数值相加导致溢出。普通矩阵幂统计路径条数,与此处最小值加法递推不同。

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

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

三种最短路径算法比较,原书P237。
对应练习
关联知识
原书对照
展开原书对照截图

