最短路径---Floyd算法

序言

此算法适用于有向图和无向图。能求出图中任一某点的最短距离。算法的时间复杂度为O(N3),空间复杂度为O(N2)

算法思想原理

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的最短路径的距离。 状态转移公式就是Dis(i,j) = Min{Dis(i,k) + Dis(k,j),Dis(i,j)}。

算法描述:

a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。 b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

算法理解

如我要求i点到j点的距离。顶点K作为中间中转点,Dis(i,k) + Dis(k,j)是多少呢。Dis(k,j)的最小值是多少呢,这不又回到上一个问题了求Dis(i,j)。动态规划抽象就抽象在这里。 所以我们要对所有可能的距离都进行动态规划。如图 floyd

  1. 列出顶点的所有可能二元组,自己到自己不算。这里为 {0,1},{0,2},{0,3},{1,0},{1,2},{1,3},{2,0},{2,1},{2,3},{3,0},{3,1},{3,2}
  2. 将v0取出来作为中转点,执行以下过程 2.1 用i,j两个变量分别指向二元组里的两个元素,比如{0,1}这个二元组,i指向0;j指向1 2.2 判断A[i][j] > A[i][0] + A[0][j]吗?如果表达式为真,进入3.3;假进入3.4 3.3 更新A[i][j]的值为A[i][0] + A[0][j] 3.4 进入下一个二元组
  3. 最后得到A矩阵就是最短距离。

代码实现

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: 带带蓝蜗牛
  • 本文链接: 273.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!