图的最短路径 - 佛洛伊德演算法 - DAY 27

前言

这篇的理解自己花了一些时间，但还是有点没把握，尽可能把理解到的内容输出。如有错误烦请指教，真心感谢。

节点和路径图

各节点至邻近节点的权重图

前驱矩阵 (查询後理解为：两个节点最佳距离会经过的节点)[如有错误烦请指出~~真的感谢]

执行步骤

上面看到的权重图节点只知道节点周围的节点
这边要逐一开放节点，直到最後跑完所有节点

STEP 1

开放 A节点，但对其他节点没有构成影响

STEP 2

开放 B节点

A节点可以透过 B节点，进而拥有到达 C、D节点的权重

此时最佳连结也会由 开放的 B节点 替换上去

STEP 3

开放 C节点

A、B节点 都可以透过 C节点，连结到 D节点，进而取得权重

被取代的位置，也对应的由 C节点去替换

完成

开放D、E节点基本已经没有影响了，故到此结束。

这个范例单纯让大家了解整体运作流程，可以往下面看一下参考来源，里面会有 找到更好的路径权重，进而替换的状况产生，可以更了解整个演算法的面貌。

参考来源

• [1]大话资料结构
• [2]6.11最短路径问题 Floyd算法
  https://www.youtube.com/watch?v=XzmTiO3j6p0
• [3]数据结构（五）图---最短路径（弗洛伊德算法）
  https://www.cnblogs.com/ssyfj/p/9495960.html