Floyd 算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点 i 到点 j 的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释 从任意节点 i 到任意节点 j 的最短路径不外乎 2 种可能:
1.直接从 i 到 j,
2.从 i 经过若干个节点 k 到 j。 所以,我们假设 Dis(i,j)为节点 u 到节点 v 的最短路径的距离,对于每一个节点 k,我们检查 Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短,我们便设置 Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点 k,Dis(i,j)中记录的便是 i 到 j 的最短路径的距离。
算法描述:
a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。 b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。